Skip to main content
Talentd

Minimum Number of Pushes to Type Word II - Solution & Explanation

MediumHash TableStringGreedySorting12 min readAsked at: Amazon, Bloomberg, De Shaw
Practice this problem

Problem Statement

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 <= 105
  • word consists of lowercase English letters.

Approach Overview

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 1: Greedy Frequency Mapping

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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`.

Try this approach in the editor →

Approach 2: Dynamic Key Allocation

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.

Code

CJava

C

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Greedy Algorithm + Sorting

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).
Space Complexity: O(k), where k is the number of unique letters stored in `frequency`.

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).
Space Complexity: O(1), as it uses fixed-size auxiliary space irrespective of input size.

Greedy Algorithm + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Frequency MappingO(n + 26 log 26)O(1)Best general solution. Simple frequency count followed by greedy assignment.
Dynamic Key AllocationO(n + 26 log 26)O(1)Useful when modeling the keypad layout explicitly or implementing step‑by‑step key distribution.

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 II easy or hard?
Minimum Number of Pushes to Type Word II is rated Medium difficulty on LeetCode. The implementation is straightforward once you recognize the greedy pattern, but identifying that frequency-based assignment minimizes total cost is the key insight.
Minimum Number of Pushes to Type Word II Python/Java solution
A Python or Java solution typically counts character frequencies, sorts them in descending order, and iterates through the sorted list while computing cost using index // 8 + 1. Each frequency is multiplied by its push cost to accumulate the final minimum total pushes.
How to solve Minimum Number of Pushes to Type Word II in O(n)?
Compute the frequency of each letter in the word using a fixed array of size 26. Sort the frequencies in descending order and assign push costs based on position using the formula index // 8 + 1. Multiply each frequency by its assigned cost and sum the results to get the minimum total pushes.
What is the best approach for Minimum Number of Pushes to Type Word II?
The greedy frequency approach is the most efficient solution. Count how many times each letter appears, sort the frequencies in descending order, and assign the most frequent letters to the cheapest push positions. The first 8 letters cost 1 push, the next 8 cost 2 pushes, and so on. This minimizes the total pushes required to type the word.
Is Minimum Number of Pushes to Type Word II asked at Google/Amazon/Meta?
Greedy frequency optimization problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. While the exact problem may vary, the pattern of assigning high-frequency elements to low-cost slots is a common interview concept.
What data structure is used in Minimum Number of Pushes to Type Word II?
The main data structures are a frequency array or hash table to count characters and a sorted list of frequencies. The algorithm then uses simple greedy allocation logic to assign push costs.
What is the time complexity of Minimum Number of Pushes to Type Word II?
The time complexity is O(n + 26 log 26), where n is the length of the word. Counting character frequencies takes O(n), and sorting at most 26 values takes O(26 log 26), which is effectively constant. Space complexity is O(1) because the alphabet size is fixed.

Ready to solve this problem?

Practice Minimum Number of Pushes to Type Word II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Letter Combinations of a Phone Number