Problem

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.

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 = "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.

Solution

Method 1 - Frequency count and sorting

We can take following steps:

  1. Count the frequency of each character in the string.
  2. Sort the frequencies in descending order.
  3. Assign the frequencies to the appropriate number of key presses:
    • The first 8 frequencies will use 1 key press.
    • The next 8 frequencies will use 2 key presses.
    • The next 8 frequencies will use 3 key presses, and so on.
  4. Multiply the character counts by the corresponding key hits to get the final answer.

Video Explanation

Here is the video explanation:

Code

Java
class Solution {
    public int minimumPushes(String word) {
        int[] freq = new int[26];
        for (int i = 0; i < word.length(); i++) {
            freq[word.charAt(i)-'a']++;
        }

        Arrays.sort(freq);

		// Array of counts representing the slots for key presses 1 through 4
		int[] counts = {8, 8, 8, 2};
		int i = 25, ans = 0, presses = 1;
        for (int count : counts) {
            while (i >= 0 && freq[i] != 0 && count > 0) {
                ans += presses * freq[i];
                count--;
                i--;
            }
            presses++;
        }
        
        return ans;
    }
}
Python
def minimum_pushes(word: str) -> int:
    from collections import Counter

    # Count the frequency of each letter
    freq = [0] * 26
    for char in word:
        freq[ord(char) - ord("a")] += 1

    # Sort the frequency array in descending order
    freq.sort(reverse=True)

    ans = 0
    i = 0
    presses = 1

    # Array of counts representing the slots for key presses 1 through 4
    counts = [8, 8, 8, 2]

    # Iterate through each set of counts and calculate the minimum presses
    for count in counts:
        while i < 26 and freq[i] != 0 and count > 0:
            ans += presses * freq[i]
            count -= 1
            i += 1
        presses += 1

    return ans

Complexity

  • ⏰ Time complexity: O(n)
    • We first go through word to create frequency map, that takes O(n)
    • Then, assigning the letter and counting takes O(26) time, i.e.O(1)
  • 🧺 Space complexity: O(1)

Method 2 - Using Frequency map and Max Heap

To solve this problem, we need to find a way to map the letters to the keys such that the total number of pushes required to type the given string word is minimized. Here’s a clear plan to achieve that:

  1. Frequency Count:
    • First, count the frequency of each letter in the word. This tells us how many times each letter appears.
  2. Sort by Frequency:
    • Sort the letters by their frequency in descending order. This way, the most frequent letters will be assigned to the keys that require the fewest presses.
  3. Assign Letters to Keys:
    • Start assigning the letters to keys from 2 to 9, distributing the letters to each key in a way that minimizes the total number of presses.

Code

Java
class Solution {
    public static int minPushesToType(String word) {
        // Step 1: Count frequency of each letter
        Map <Character, Integer> frequencyMap = new HashMap<>();
        for (char c: word.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // Step 2: Use a max heap to sort frequencies in descending order
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        for (int frequency: frequencyMap.values()) {
            maxHeap.offer(frequency);
        }

        int minPresses = 0;
        int presses = 1;

        // Step 3: Assign frequencies to keys in the order of their need of presses.
        while (!maxHeap.isEmpty()) {
            for (int i = 0; i < 8; i++) {
                // Distribute the letters among the keys
                if (maxHeap.isEmpty()) {
                    break;
                }
                int freq = maxHeap.poll();
                minPresses += freq * presses;
            }
            presses++;
        }

        return minPresses;
    }
}
Python
def min_pushes_to_type(word: str) -> int:
    from collections import Counter
    import heapq

    # Step 1: Count frequency of each letter
    frequency = Counter(word)

    # Step 2: Sort letters by frequency in descending order
    freq_list = sorted(frequency.values(), reverse=True)

    # Step 3: Calculate minimum presses needed
    min_presses = 0

    # Highest priority values should be pushed to the front
    heapq.heapify(freq_list)  # Convert list to a min heap

    presses = 1
    while freq_list:
        for _ in range(8):  # Distribute the letters among the keys
            if not freq_list:
                break
            min_presses += heapq.heappop(freq_list) * presses
        presses += 1

    return min_presses

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)
    • We are storing only 26 letters in maxheap