SAC '22 Code Challenge 5 Junior P5 - English Summative

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 1.5s
Python 1.5s
Memory limit: 256M
Python 1G

Problem type

Max has been procrastinating on his English summative and needs help finishing it.

Since Max knows his teacher loves alliterations, he would also love when two consecutive characters are the same in a string.

Max has written N words, S_i, for his summative most of which are gibberish but needs you to clean it up for him to maximize his summative mark.

A string can be derived from these N words by selecting some (or all) of them and concatenating them together without changing the order.

The score of a string is determined by the number of two-letter substrings that only use one character.

This score determines his summative mark.

Can you help Max find out his maximum summative mark?


1 \le N \le 2 \times 10^5

1 \le |S_i| \le 5

Note that |S_i| denotes the length of the string S_i.

S_i will only contain lowercase letters.

Subtask 1 [20%]

1 \le N \le 20

Subtask 2 [40%]

1 \le N \le 1\,000

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line will contain an integer, N, the number of words.

The next N lines will contain a word, S_i, the i^\text{th} word.

Output Specification

Output the maximum score (i.e., the maximum number of two-letter substrings that only use one character from a subsequence of the N words).

Sample Input


Sample Output


Explanation for Sample Output

If the first, third, fourth, and fifth words are concatenated, the final string is roooyooort, and there are 4 substrings that two-letter substrings that have the same character: [2, 3], [3, 4], [6, 7], [7, 8]. It can be proven that this is the maximum score.


There are no comments at the moment.