Fewest Keypresses After Remapping Distinct Letters

# Fewest Keypresses After Remapping Distinct Letters You are given a string `word` whose lowercase English letters are all distinct. You may remap the eight telephone keys numbered `2` through `9`. Each key holds an ordered list of letters. A letter in the first position costs one push to type, a letter in the second position costs two pushes, and so on. For example, if key `2` holds `[a,b,c]`, typing `c` costs three pushes. Each letter must be assigned to exactly one key. A key may hold any number of letters, and not every key needs to be used. Keys `1`, `0`, `*`, and `#` cannot hold letters. The mapping is chosen for the whole word; you do not change it between characters. Return the minimum total number of pushes needed to type `word`. You do not need to return the mapping. Letters absent from `word` contribute no typing cost and can be placed after the used letters. ### Examples **Example 1** ```text Input: word = "mnopqrstu" Output: 10 ``` One optimal mapping places `m,n,o,p,q,r,s,t` first on keys `2,3,4,5,6,7,8,9`, respectively, and places `u` second on key `2`. The used letters cost `1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 10` pushes. **Example 2** ```text Input: word = "abcdefghijklmnopq" Output: 27 ``` One optimal mapping places `[a,i,q]` on key `2`, `[b,j]` on key `3`, `[c,k]` on key `4`, and similarly `[d,l]`, `[e,m]`, `[f,n]`, `[g,o]`, `[h,p]` on keys `5` through `9`. The total is `8 * 1 + 8 * 2 + 1 * 3 = 27`. Any other alphabet letters can follow these listed letters without affecting this cost. ### Constraints - `1 <= word.length <= 26`. - `word` contains only lowercase English letters. - All letters in `word` are distinct. ### Clarifying Questions - Must the usual telephone letter layout be kept? No; you may choose a new assignment and letter order on keys `2..9`. - Is there a limit of three or four letters per key? No; keys may hold any number of letters. - Must all eight letter keys be nonempty? No. - Does each character in this version occur once? Yes; distinct letters are guaranteed by the input contract. - Is a particular optimal mapping required as output? No; return only the minimum push count. ### C++ Interface ```cpp class Solution { public: int minimumPushes(string word) { } }; ``` ### Reasoning Checkpoints - Apply the stated per-letter push cost to a legal assignment using only keys `2..9`. - Preserve the distinct-letter guarantee and justify that the returned total is minimal. - Explain the time and space costs under the stated bounds. ```hint Count the available positions at each push cost There are eight first positions, eight second positions, and so on. Every used letter occurs once, so consider how many of the cheapest positions are needed for the word's length. ```