Minimum Number of Pushes to Type Word I

Difficulty: Easy | Acceptance: 67.10% | Paid: No Topics: Math, String, Greedy

You are given a string word containing lowercase English letters.

In a standard phone keypad (like the one shown below), each letter is mapped to a digit. To type a letter, you need to press the corresponding key multiple times. For example, to type ‘a’, you press key ‘2’ once, to type ‘b’, you press key ‘2’ twice, and so on.

However, you are allowed to remap the letters to the keys in any way you want. The only constraint is that each key (2-9) can have at most one letter assigned to each position (1st, 2nd, 3rd, or 4th press).

Return the minimum number of pushes required to type the given word.

• Examples
• Constraints
• Greedy with Frequency Array
• Using Hash Map
• Priority Queue Approach

Examples

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

Greedy with Frequency Array

Intuition To minimize total pushes, assign the most frequent letters to keys requiring fewer presses. With 8 keys, the first 8 letters need 1 push, next 8 need 2 pushes, and so on.

Steps

• Count frequency of each character using a fixed-size array of 26
• Sort frequencies in descending order
• Calculate total pushes: position = index // 8 + 1, multiply by frequency

class Solution:
    def minimumPushes(self, word: str) -> int:
        freq = [0] * 26
        for c in word:
            freq[ord(c) - ord('a')] += 1
        
        freq.sort(reverse=True)
        
        total = 0
        for i in range(26):
            if freq[i] == 0:
                break
            position = i // 8 + 1
            total += position * freq[i]
        
        return total

Complexity

• Time: O(n + 26 log 26) = O(n)
• Space: O(26) = O(1)
• Notes: Most efficient with fixed array size

Using Hash Map

Intuition Use a hash map to count character frequencies, then sort only the non-zero frequencies for potentially better performance with sparse inputs.

Steps

• Count character frequencies using a hash map
• Extract and sort frequencies in descending order
• Calculate total pushes based on position

from collections import Counter

class Solution:
    def minimumPushes(self, word: str) -> int:
        freq = Counter(word)
        
        sorted_freq = sorted(freq.values(), reverse=True)
        
        total = 0
        for i, count in enumerate(sorted_freq):
            position = i // 8 + 1
            total += position * count
        
        return total

Complexity

• Time: O(n + k log k) where k is number of unique characters
• Space: O(k) for the hash map
• Notes: More memory efficient for words with few unique characters

Priority Queue Approach

Intuition Use a max heap to efficiently retrieve the highest frequency characters one at a time, assigning them to optimal positions.

Steps

• Count character frequencies
• Build a max heap with non-zero frequencies
• Pop frequencies one by one, calculating pushes based on position

import heapq

class Solution:
    def minimumPushes(self, word: str) -> int:
        freq = [0] * 26
        for c in word:
            freq[ord(c) - ord('a')] += 1
        
        max_heap = [-f for f in freq if f > 0]
        heapq.heapify(max_heap)
        
        total = 0
        i = 0
        while max_heap:
            position = i // 8 + 1
            count = -heapq.heappop(max_heap)
            total += position * count
            i += 1
        
        return total

Complexity

• Time: O(n + k log k) where k is number of unique characters
• Space: O(k) for the heap
• Notes: Useful when you need to process frequencies incrementally