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: The key idea is to map the most frequently occurring letters to keys such that they require fewer presses. By doing this, we can minimize the total number of key presses needed to type the word. First, count the frequency of each character in the word. Then, sort these characters by frequency in descending order. Assign them to the keys with the least number of lever pulls needed - the key with the highest frequency letters receives only one press.
This Python solution uses the Counter class from the collections module to count the frequency of each letter in the word. The frequencies are then sorted in descending order. We process each letter, assigning the most frequent ones to require only one press, using the ((i // 9) + 1) calculation to determine the number of presses for remapped keys.
Python
JavaScript
Time Complexity: O(n + k log k), where n is the length of the word and k is the number of unique letters. Sorting takes O(k log k).
Space Complexity: O(k), where k is the number of unique letters stored in `frequency`.
Approach: Allocate keys dynamically based on frequency but with a twist: instead of pre-sorting all letters, allocate keys to letters in frequency order and determine the number of presses required for each allocation. Keep track of the frequency allocation dynamically using numeric keys to reallocation.
This C solution uses an array to store the frequency of each letter. It then uses the qsort function to sort these frequencies in descending order, emulating a dynamic allocation of key mappings based on increasing frequency pull multipliers.
Time Complexity: O(n + k log k), where n is the size of the word and k is the number of possible unique letters (26).
Space Complexity: O(1), as it uses fixed-size auxiliary space irrespective of input size.
We use a hash table or array cnt to count the number of occurrences of each letter in the string word. Next, we sort the letters in descending order of their counts, and then group every 8 letters together, assigning each group to the 8 keys.
The time complexity is O(n + |\Sigma| times log |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the string word, and \Sigma is the set of letters that appear in the string word.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Greedy Frequency Mapping | Time Complexity: O(n + k log k), where n is the length of the word and k is the number of unique letters. Sorting takes O(k log k). |
| Dynamic Key Allocation | Time Complexity: O(n + k log k), where n is the size of the word and k is the number of possible unique letters (26). |
| Greedy Algorithm + Sorting | — |
| 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. |
Minimum Number of Pushes to Type Word II - Leetcode 3016 - Python • NeetCodeIO • 9,784 views views
Watch 9 more video solutions →Practice Minimum Number of Pushes to Type Word II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor