A coastal lighthouse sends messages to passing ships using a bank of exactly 8 signal shutters. Before sending anything, the keeper designs a fixed code: every letter that will be needed is assigned to exactly one shutter, and the letters assigned to a given shutter are placed in a fixed order. To flash a letter, the keeper triggers that letter's shutter a number of times equal to the letter's position within its shutter's list (the first letter assigned to a shutter costs 1 flash, the second costs 2 flashes, the third costs 3 flashes, and so on) -- and every time that letter appears in the message, it costs exactly that many flashes again.
Given the message the keeper must send, design the code -- which shutter each letter is assigned to, and in what order within the shutter -- to minimize the total number of flashes needed to send the entire message.
A single line containing the message: a string of lowercase English letters.
Print a single integer: the minimum total number of flashes needed to send the message under an optimally designed code.
1 <= length of the message <= 200000a-z).Example 1
Input
aabbccdd
Expected
8
Explanation
There are 4 distinct letters (a,b,c,d), each appearing twice. Since there are only 4 distinct letters (fewer than 8 shutters), every letter can be the first letter on its own shutter, costing 1 flash per occurrence: 4 letters x 2 occurrences x 1 flash = 8.
Example 2
Input
abcdefghi
Expected
10
Explanation
There are 9 distinct letters, each appearing once, so frequencies are all equal. Any 8 of them can occupy the first position on the 8 shutters (1 flash each = 8 total), and the 9th must share a shutter at the second position (2 flashes). Total = 8 + 2 = 10, regardless of which letter is picked as the 9th.
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 →