Fewest Keypresses After Remapping Letters That May Repeat
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Fewest Keypresses After Remapping Letters That May Repeat
You are given a string `word` of lowercase English letters. Letters may occur more than once.
You may remap the eight telephone keys numbered `2` through `9`. Each key holds an ordered list of letters. Typing a letter costs as many pushes as its 1-based position in that key's list. For example, a key holding `[a,b,c]` types `a` with one push, `b` with two, and `c` with three.
Each letter must be assigned to exactly one key. A key may hold any number of letters, and some keys may be empty. Keys `1`, `0`, `*`, and `#` cannot hold letters. Choose one mapping for the whole word and add the push cost of every character occurrence.
Return the minimum total number of pushes needed to type `word`. You do not need to return a mapping. Letters absent from `word` contribute no typing cost and can follow the used letters.
### Examples
**Example 1**
```text
Input: word = "aaaaabbbbcdefghi"
Output: 17
```
One optimal mapping places `[a,i]` on key `2`, then `b,c,d,e,f,g,h` first on keys `3` through `9`. The five `a` occurrences cost five pushes, the four `b` occurrences cost four, the six letters `c..h` cost one each, and `i` costs two: `5 + 4 + 6 + 2 = 17`.
**Example 2**
```text
Input: word = "zzzzzabcdefghijklmnop"
Output: 31
```
One optimal mapping puts `[z,h,p]` on key `2`, `[a,i]` on key `3`, `[b,j]` on key `4`, and similarly `[c,k]`, `[d,l]`, `[e,m]`, `[f,n]`, `[g,o]` on keys `5` through `9`. The five `z` occurrences and seven letters `a..g` cost twelve pushes, the eight letters `h..o` cost sixteen, and `p` costs three, totaling `31`. Any absent letters can be appended after the listed letters.
### Constraints
- `1 <= word.length <= 10^5`.
- `word` contains only lowercase English letters.
### Clarifying Questions
- Are letters guaranteed to be distinct? No; every occurrence contributes to the total typing cost.
- Can a repeated letter be assigned to several keys? No; each letter has one assigned key and position for the whole word.
- Must the usual telephone layout or alphabetic order be retained? No; both key assignment and letter order may change.
- Must every usable key be nonempty? No, and there is no fixed limit on letters per key.
- Is the task to output the remapping? No; return only its minimum total push count.
### C++ Interface
```cpp
class Solution {
public:
int minimumPushes(string word) {
}
};
```
### Reasoning Checkpoints
- Include every occurrence using one consistent legal mapping for each letter.
- Justify that the returned total cannot be improved by another legal mapping.
- Account for the entire input length and possible numeric range in the complexity and arithmetic analysis.
```hint Match occurrence counts to push costs
There are eight positions at each positive push cost. Count how often each letter occurs, then consider which letters should receive the cheaper positions. An exchange of two letters can help justify that choice.
```
Overview: Minimize the total keypress cost of a lowercase word with repeated letters under one remapping of eight telephone keys, counting every occurrence.
