Compute the minimum number of key presses needed to type a word when each letter can be assigned to a limited set of keypad positions.
Minimum Number of Pushes to Type Word II
You are given a word consisting of lowercase English letters. Imagine a simple phone keypad where each key can hold multiple letters, and the number of pushes needed to type a letter depends on how many letters have been assigned to earlier positions on that keypad.
Your goal is to assign the letters in the word to keypad positions so that the total number of pushes required to type the whole word is as small as possible.
A good strategy is to place the most frequent letters in the cheapest positions and the less frequent letters in more expensive positions.
Return the minimum total number of pushes required.
Key idea
If a position costs 1 push, the next set costs 2 pushes, and so on, then the optimal assignment is driven by letter frequencies rather than by the original order of the word.
Input Format
- A single string
wordcontaining lowercase English letters. - The string may contain repeated characters.
Output Format
- Return one integer: the minimum number of pushes needed to type
wordunder the optimal assignment.
Constraints
1 <= word.length <= $10^{5}$wordcontains only lowercase English letters- The answer fits in a 32-bit signed integer
Example 1
Input
word = "abcde"
Output
5
Explanation
Each letter appears once, so all letters can be assigned to the cheapest positions. The minimum total is 1 + 1 + 1 + 1 + 1 = 5.
Example 2
Input
word = "aabbcc"
Output
6
Explanation
There are three letters, each appearing twice. Assign them to the cheapest positions, so the total is 2 + 2 + 2 = 6.
Show 1 more example
Example 3
Input
word = "zzzz"
Output
4
Explanation
Only one letter is used, so every occurrence costs 1 push. The total is 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.