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 words, , 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 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?
Note that denotes the length of the string .
will only contain lowercase letters.
Subtask 1 [20%]
Subtask 2 [40%]
Subtask 3 [40%]
No additional constraints.
The first line will contain an integer, , the number of words.
The next lines will contain a word, , the word.
Output the maximum score (i.e., the maximum number of two-letter substrings that only use one character from a subsequence of the words).
5 ro r oo yo oort
Explanation for Sample Output
If the first, third, fourth, and fifth words are concatenated, the final string is
roooyooort, and there are substrings that two-letter substrings that have the same character: . It can be proven that this is the maximum score.