Watch 10 video solutions for Minimum Number of Pushes to Type Word I, a easy level problem involving Math, String, Greedy. This walkthrough by codestorywithMIK has 9,530 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 26word consists of lowercase English letters.word are distinct.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 | 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. |