Watch 10 video solutions for Minimum Number of Pushes to Type Word II, a medium level problem involving Hash Table, String, Greedy. This walkthrough by NeetCodeIO has 9,784 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string word containing lowercase English letters.
Telephone keypads have keys mapped with distinct collections of lowercase English letters, which can be used to form words by pushing them. For example, the key 2 is mapped with ["a","b","c"], we need to push the key one time to type "a", two times to type "b", and three times to type "c" .
It is allowed to remap the keys numbered 2 to 9 to distinct collections of letters. The keys can be remapped to any amount of letters, but each letter must be mapped to exactly one key. You need to find the minimum number of times the keys will be pushed to type the string word.
Return the minimum number of pushes needed to type word after remapping the keys.
An example mapping of letters to keys on a telephone keypad is given below. Note that 1, *, #, and 0 do not map to any letters.
Example 1:
Input: word = "abcde" Output: 5 Explanation: The remapped keypad given in the image provides the minimum cost. "a" -> one push on key 2 "b" -> one push on key 3 "c" -> one push on key 4 "d" -> one push on key 5 "e" -> one push on key 6 Total cost is 1 + 1 + 1 + 1 + 1 = 5. It can be shown that no other mapping can provide a lower cost.
Example 2:
Input: word = "xyzxyzxyzxyz" Output: 12 Explanation: The remapped keypad given in the image provides the minimum cost. "x" -> one push on key 2 "y" -> one push on key 3 "z" -> one push on key 4 Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12 It can be shown that no other mapping can provide a lower cost. Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.
Example 3:
Input: word = "aabbccddeeffgghhiiiiii" Output: 24 Explanation: The remapped keypad given in the image provides the minimum cost. "a" -> one push on key 2 "b" -> one push on key 3 "c" -> one push on key 4 "d" -> one push on key 5 "e" -> one push on key 6 "f" -> one push on key 7 "g" -> one push on key 8 "h" -> two pushes on key 9 "i" -> one push on key 9 Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24. It can be shown that no other mapping can provide a lower cost.
Constraints:
1 <= word.length <= 105word consists of lowercase English letters.Problem Overview: You need to type a word using a phone keypad with 8 available keys (2–9). Each key can contain multiple characters, and the number of pushes required equals the character’s position on that key. The goal is to assign letters to keys so the total pushes needed to type the given word is minimized.
Approach 1: Greedy Frequency Mapping (O(n + 26 log 26) time, O(1) space)
Count how often each character appears in the word, then assign the most frequent letters to the cheapest key positions. The keypad effectively has 8 slots that cost 1 push, the next 8 slots cost 2 pushes, the next 8 cost 3 pushes, and the remaining slots cost 4 pushes. After computing character frequencies with a fixed-size array or hash table, sort the frequencies in descending order using sorting. Iterate through the sorted list and multiply each frequency by its push cost using cost = index // 8 + 1. This greedy assignment works because placing higher-frequency characters in cheaper positions minimizes the global total.
This method is optimal since there are only 26 lowercase letters. Sorting at most 26 values is effectively constant time. The algorithm scales linearly with the word length for counting plus a tiny constant overhead for sorting.
Approach 2: Dynamic Key Allocation (O(n + 26 log 26) time, O(1) space)
Another way to model the same idea is to simulate the keypad layout directly. First compute frequencies of all characters using a counting array (a classic counting technique). Sort characters by frequency in descending order. Instead of computing the cost mathematically, dynamically assign characters to keys one by one while tracking how many letters each key currently holds.
Each key accepts characters in layers: the first layer costs 1 push, the second layer costs 2 pushes, and so on. When distributing characters across keys, you fill all 8 keys at push level 1 before moving to push level 2. This allocation mirrors the physical keypad behavior and can be easier to visualize during implementation in languages like C or Java.
Recommended for interviews: The greedy frequency approach is what interviewers expect. It shows you recognize the optimization pattern: prioritize high-frequency elements for the lowest cost slots. Demonstrating the counting step and the index // 8 + 1 cost calculation proves you understand both the greedy reasoning and the keypad constraints.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Frequency Mapping | O(n + 26 log 26) | O(1) | Best general solution. Simple frequency count followed by greedy assignment. |
| Dynamic Key Allocation | O(n + 26 log 26) | O(1) | Useful when modeling the keypad layout explicitly or implementing step‑by‑step key distribution. |