Minimum Number of Pushes to Type Word I - Solution & Explanation
Problem Statement
You are given a string word containing distinct 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 = "xycdefghij" Output: 12 Explanation: The remapped keypad given in the image provides the minimum cost. "x" -> one push on key 2 "y" -> two pushes on key 2 "c" -> one push on key 3 "d" -> two pushes on key 3 "e" -> one push on key 4 "f" -> one push on key 5 "g" -> one push on key 6 "h" -> one push on key 7 "i" -> one push on key 8 "j" -> one push on key 9 Total cost is 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12. It can be shown that no other mapping can provide a lower cost.
Constraints:
1 <= word.length <= 26wordconsists of lowercase English letters.- All letters in
wordare distinct.
Approach Overview
Problem Overview: You need to type a word using a phone keypad with 8 keys. Each key can contain multiple letters, and the number of pushes required equals the letter's position on its key (first letter = 1 push, second = 2 pushes, etc.). You can remap letters to any key. The goal is to assign letters so the total number of pushes needed to type the given word is minimized.
Approach 1: Greedy Mapping by Frequency (O(n + 26 log 26) time, O(1) space)
Count the frequency of each character in the word, then sort the frequencies in descending order. The key insight: letters used more often should require fewer pushes. Since there are 8 keys, the first 8 most frequent letters cost 1 push each, the next 8 cost 2, the next 8 cost 3, and the remaining letters cost 4. Iterate through the sorted frequencies and multiply each frequency by its push cost tier. This greedy assignment works because minimizing the push cost of high‑frequency letters always reduces the total operations. The algorithm mainly uses frequency counting from a string and a simple greedy ordering from greedy optimization principles.
Approach 2: Dynamic Partitioning Approach (O(26 * 26) time, O(26) space)
Another way to think about the problem is to decide how many letters should receive cost 1, 2, 3, and 4 pushes. With 8 keys available per level, the assignment becomes a partitioning problem across frequency values. Sort the character frequencies and evaluate partitions where the first group has cost 1, the next cost 2, and so on. A small dynamic programming or prefix-sum based evaluation can compute the minimal weighted cost across these partitions. Because the alphabet size is fixed (26), the computation remains constant time in practice. This perspective frames the problem as a cost minimization problem using simple arithmetic from math and frequency grouping.
Recommended for interviews: The greedy frequency mapping approach is what interviewers expect. It shows you recognize that higher-frequency characters should get cheaper operations. Counting frequencies and assigning push costs in sorted order is straightforward, optimal, and runs in linear time relative to the input length. Mentioning the partitioning perspective shows deeper understanding, but the greedy method demonstrates the strongest algorithmic intuition.
Approach 1: Greedy Mapping Approach
This approach involves using a greedy strategy where we try to distribute the letters across the available keys such that the number of key presses is minimized. Each key can have multiple letters mapped to it but typing a letter takes a number of pushes equivalent to its position in the key sequence. Start mapping from the letter requiring the most pushes to minimize push count overall.
This solution sorts the given word alphabetically first, then assigns each letter to the best possible key. Each key can support 9 letters maximally, so each letter's press count is determined by its position modulated over 9.
Complexity
Time Complexity: O(n log n) - Due to the sorting operation.
Space Complexity: O(1) - Only uses constant space for variables.
Approach 2: Dynamic Partitioning Approach
In this approach, we consider treating the distribution of letters to keys as a dynamic programming problem. The aim is to find subsets of letters that can be optimally packed into a series of 9-slot keys (since each key can host up to 9 letters with minimal pushes needed as explained earlier) with consideration to minimize excess steps due to larger partitioning of letters repeatedly.
This C solution utilizes dynamic programming to find the optimal partition places for slicing the word into sections of up to 9 characters to be mapped sequentially to keys, limiting excessive presses by optimizing each key segment use.
Complexity
Time Complexity: O(n * 9) - Nine possible slice sizes checked for each character index.
Space Complexity: O(n) - Space for dynamic programming table.
Approach 3: Greedy Algorithm
We notice that all the letters in the string word are different. Therefore, we can greedily distribute the letters evenly across the 8 keys to minimize the number of key presses.
The time complexity is O(n / 8), where n is the length of the string word. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Mapping Approach | Time Complexity: O(n log n) - Due to the sorting operation. |
| Dynamic Partitioning Approach | Time Complexity: O(n * 9) - Nine possible slice sizes checked for each character index. |
| Greedy Algorithm | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Mapping by Frequency | O(n + 26 log 26) | O(1) | Best general solution. Assign cheapest push counts to the most frequent letters. |
| Dynamic Partitioning Approach | O(26 * 26) | O(26) | Useful for reasoning about push-cost groups or exploring cost partitioning strategies. |
Video Solution
Minimum Number of Pushes to Type Word I and II | Leetcode 3014 | Leetcode 3016 | Weekly Contest • codestorywithMIK • 9,977 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Number of Pushes to Type Word I easy or hard?
Minimum Number of Pushes to Type Word I Python/Java solution
How to solve Minimum Number of Pushes to Type Word I in O(n)?
What is the best approach for Minimum Number of Pushes to Type Word I?
Is Minimum Number of Pushes to Type Word I asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Pushes to Type Word I?
What is the time complexity of Minimum Number of Pushes to Type Word I?
Ready to solve this problem?
Practice Minimum Number of Pushes to Type Word I with our built-in code editor and test cases.
Practice on FleetCode