A freight yard uses handheld scanner guns with a compact 9-button keypad to enter item manifest codes made of lowercase letters. Because there are 26 possible letters but only 9 physical buttons, several letters must share a button; a button assigned k letters requires the operator to tap it once to select its 1st assigned letter, twice in a row for its 2nd assigned letter, three times for its 3rd, and so on — typing a letter that sits in the j-th position on its button costs j taps every time that letter occurs. Before scanning today's manifest string, the yard supervisor is free to choose which letters go on which button and in what order, purely to minimize the cost of entering today's string (a letter that never appears in the string can simply be left off every button). Choosing the layout optimally for the given manifest string s, determine the minimum total number of taps needed to enter s.
A single line containing the string s.
Print a single integer: the minimum total number of taps.
Example 1
Input
banana
Expected
6
Explanation
The letters are a (3 times), n (2 times), b (1 time) — only 3 distinct letters, so all three can sit in the 1-tap position on three different buttons. Cost = 3*1 + 2*1 + 1*1 = 6. Output: 6.
Example 2
Input
aaaaabbbbccccdddeeeffgghhij
Expected
28
Explanation
Frequencies sorted descending are a=5, b=4, c=4, d=3, e=3, f=2, g=2, h=2, i=1, j=1 — 10 distinct letters. The 9 most frequent (a through i) can each take the 1-tap position on 9 different buttons, costing 5+4+4+3+3+2+2+2+1 = 26. The 10th letter, j, must take a 2-tap position on one of those buttons, costing 1*2 = 2. Total = 26 + 2 = 28. Output: 28.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →