Minimum Number of Pushes to Type Word II

Med

#2684Time: O(N + K^2), where N is the length of the word and K is the number of unique characters. Counting frequencies takes O(N). The main loop runs K times. Inside the loop, finding the maximum frequency takes O(K) and removing an element from an `ArrayList` can also take O(K). This results in an O(K^2) complexity for the assignment part. Since K is at most 26, K^2 is a small constant, so the overall complexity is dominated by O(N).Space: O(K), for the frequency map and the list of frequencies, where K is the number of unique characters. Since K <= 26, this is O(1) constant space.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach follows a greedy strategy. The core idea is that characters with higher frequencies should be assigned to key positions that require fewer pushes. To minimize the total pushes, we should assign the most frequent character to a 1-push position, the second most frequent to another 1-push position, and so on, until all 8 1-push positions are filled. Then we move to 2-push positions. This approach implements this strategy by repeatedly finding the character with the current maximum frequency and assigning it to the next available cheapest slot.

Algorithm

Create a frequency map (e.g., HashMap<Character, Integer>) to store the counts of each character in word.
Iterate through word and populate the frequency map.
Create a list containing all the frequency values from the map.
Initialize totalPushes = 0 and assignedCount = 0.
While the list of frequencies is not empty:
- Find the maximum frequency in the list.
- Determine the cost for this character. The cost is (assignedCount / 8) + 1.
- Add maxFrequency * cost to totalPushes.
- Remove the maximum frequency from the list.
- Increment assignedCount.
Return totalPushes.

Walkthrough

First, we count the frequency of each character in the input string word. A hash map or an array of size 26 can be used for this. We then extract the frequencies of the unique characters into a list. We loop as many times as there are unique characters. In each iteration, we find the maximum frequency in our list, calculate its contribution to the total pushes, and then remove it from consideration for the next iteration (e.g., by setting its value to 0 or removing it from the list). The cost (number of pushes) for each character is determined by its rank in the sorted frequency order. The first 8 characters get a cost of 1, the next 8 get a cost of 2, and so on. We keep track of how many characters have been assigned to determine the current cost.

1import java.util.*;2 3class Solution {4    public int minimumPushes(String word) {5        Map<Character, Integer> freqMap = new HashMap<>();6        for (char c : word.toCharArray()) {7            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);8        }9 10        List<Integer> frequencies = new ArrayList<>(freqMap.values());11        12        int totalPushes = 0;13        int assignedCount = 0;14        15        while (!frequencies.isEmpty()) {16            int maxFreq = 0;17            int maxIndex = -1;18            19            for (int i = 0; i < frequencies.size(); i++) {20                if (frequencies.get(i) > maxFreq) {21                    maxFreq = frequencies.get(i);22                    maxIndex = i;23                }24            }25            26            int pushes = (assignedCount / 8) + 1;27            totalPushes += maxFreq * pushes;28            29            frequencies.remove(maxIndex);30            assignedCount++;31        }32        33        return totalPushes;34    }35}

Complexity

Time

O(N + K^2), where N is the length of the word and K is the number of unique characters. Counting frequencies takes O(N). The main loop runs K times. Inside the loop, finding the maximum frequency takes O(K) and removing an element from an `ArrayList` can also take O(K). This results in an O(K^2) complexity for the assignment part. Since K is at most 26, K^2 is a small constant, so the overall complexity is dominated by O(N).

Space

O(K), for the frequency map and the list of frequencies, where K is the number of unique characters. Since K <= 26, this is O(1) constant space.

Trade-offs

Pros

Conceptually simple greedy logic.
Correctly solves the problem.

Cons

The O(K^2) part is less efficient than a sorting-based approach. Repeatedly scanning the list to find the maximum is suboptimal.

This is an optimized version of the greedy strategy. Instead of repeatedly finding the maximum frequency, we can determine the optimal assignment more efficiently. The key insight remains the same: characters with higher frequencies must be assigned to positions with fewer pushes. By sorting all character frequencies in descending order, we can directly map the most frequent characters to the cheapest slots.

Algorithm

Create a frequency array freq of size 26, initialized to zeros.
Iterate through the input word and increment the count for each character in the freq array (freq[c - 'a']++).
Create a list to store the non-zero frequencies from the freq array.
Sort this list of frequencies in descending order.
Initialize totalPushes = 0.
Iterate through the sorted list with index i from 0 to list.size() - 1:
- Get the frequency f at index i.
- The number of pushes for this character is (i / 8) + 1.
- Add f * ((i / 8) + 1) to totalPushes.
Return totalPushes.

Walkthrough

First, we count the frequency of each character. An array of size 26 is a highly efficient way to do this for lowercase English letters. We then collect all the non-zero frequencies. We sort these frequencies in descending order. This places the characters that appear most often at the beginning of our sorted list. Finally, we iterate through the sorted list of frequencies. The first 8 frequencies correspond to characters that will be assigned to 1-push slots. The next 8 will be assigned to 2-push slots, and so on. The cost for a character at index i in the sorted list is (i / 8) + 1. We calculate the total pushes by summing up frequency * cost for each frequency in the list.

1import java.util.*;2 3class Solution {4    public int minimumPushes(String word) {5        int[] freq = new int[26];6        for (char c : word.toCharArray()) {7            freq[c - 'a']++;8        }9 10        List<Integer> frequencies = new ArrayList<>();11        for (int f : freq) {12            if (f > 0) {13                frequencies.add(f);14            }15        }16 17        // Sort frequencies in descending order18        Collections.sort(frequencies, Collections.reverseOrder());19 20        int totalPushes = 0;21        for (int i = 0; i < frequencies.size(); i++) {22            int f = frequencies.get(i);23            int pushes = (i / 8) + 1;24            totalPushes += f * pushes;25        }26 27        return totalPushes;28    }29}

Complexity

Time

O(N + K log K), where N is the length of the word and K is the number of unique characters. Counting frequencies takes O(N). Collecting non-zero frequencies takes O(1) (since we iterate through a 26-element array). Sorting the K frequencies takes O(K log K). Calculating the final sum takes O(K). Since K <= 26, K log K is a small constant, so the overall complexity is effectively O(N).

Space

O(K), for the frequency array and the list to be sorted, where K is the number of unique characters. Since K <= 26, this is O(1) constant space.

Trade-offs

Pros

Highly efficient, representing the optimal solution.
The logic is clean and directly implements the greedy strategy.
Using an array for frequency counting is faster than a hash map for this problem.

Cons

Requires sorting, which might be slightly more complex to implement from scratch compared to the repeated search, but standard library functions make it trivial.

Solutions

Solution

1class Solution {2public3  int minimumPushes(String word) {4    int[] cnt = new int[26];5    for (int i = 0; i < word.length(); ++i) {6      ++cnt[word.charAt(i) - 'a'];7    }8    Arrays.sort(cnt);9    int ans = 0;10    for (int i = 0; i < 26; ++i) {11      ans += (i / 8 + 1) * cnt[26 - i - 1];12    }13    return ans;14  }15}

1function minimumPushes ( word ) { const cnt = Array ( 26 ). fill ( 0 ); for ( const c of word ) { ++ cnt [ c . charCodeAt ( 0 ) - ' a ' . charCodeAt ( 0 )]; } cnt . sort (( a , b ) => b - a ); let ans = 0 ; for ( let i = 0 ; i < 26 ; ++ i ) { ans += ((( i / 8 ) | 0 ) + 1 ) * cnt [ i ]; } return ans ; }

1class Solution {2public:3  int minimumPushes(string word) {4    vector<int> cnt(26);5    for (char &c : word) {6      ++cnt[c - 'a'];7    }8    sort(cnt.rbegin(), cnt.rend());9    int ans = 0;10    for (int i = 0; i < 26; ++i) {11      ans += (i / 8 + 1) * cnt[i];12    }13    return ans;14  }15};

1class Solution:2    def minimumPushes(self, word: str) -> int: cnt = Counter(word) ans = 0 for i, x in enumerate(sorted(cnt . values(), reverse=True)): ans += (i // 8 + 1) * x return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem