Solution Approach to Solve Leetcode Problem "3016. Minimum Number of Pushes to Type Word II"

In this article, we'll tackle the LeetCode problem '3016. Minimum Number of Pushes to Type Word II,' where we need to find the minimum number of pushes required to type a given word using a keyboard with a specific layout. The problem provides a keyboard layout and asks us to calculate the minimum number of pushes needed to type a given word. Each key can represent multiple characters, and we need to determine the optimal way to switch between these characters."

Problem Description

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.

Constraints:

• 1 <= word.length <= 10<sup>5</sup>

• word consists of lowercase English letters.

  Example:

    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.
  

  For more understanding please see this image.

  

  Problem link

  Solution Strategy

  The goal is to minimize the number of pushes needed to type out the word by efficiently distributing the characters across the eight available slots on the keyboard.

• Step-by-Step Breakdown:

  1. Count Character Frequencies:

• First, count the frequency of each character in the word. This helps to understand how many times each character needs to be typed.

•   map<char, int> fre;
    for (auto it : word) {
        fre[it]++;
    }
  

  2. Store Frequencies in a Vector:

• Store these frequencies in a vector, which will help in sorting and processing the characters in a specific order.

•   vector<int> res;
    for (auto it : fre) {
        res.push_back(it.second);
    }
  

  3. Sort Frequencies in Descending Order:

• Sort the vector of frequencies in descending order. By doing this, the most frequent characters are given priority in the earlier slots, reducing the total number of pushes required.

    sort(res.begin(), res.end(), greater<int>());
  

  4. Calculate Minimum Pushes:

• To calculate the minimum pushes, consider how many complete groups of 8 characters can be formed and what remains as the remainder.

• For each complete group of 8, add the frequency of each character multiplied by its position in the group (e.g., characters in the first slot contribute to fewer pushes than those in the second slot, and so on).

• For the remaining characters, multiply their frequency by the number of complete groups plus one.

    int div = res.size() / 8;
    int mod = res.size() % 8;
    int k = 1, ans = 0, last = res.size() - 1;
    for (int i = 0; i < div; i++) {
        for (int j = (i * 8); j < (i + 1) * 8; j++) {
            ans += (res[j] * k);
        }
        ++k;
    }
    while (mod--) {
        ans += (res[last] * (div + 1));
        last--;
    }
    return ans;
  

  Example to Illustrate the Solution

  Example: Let's consider the word aabbbbccddeeee.

  1. Character Frequency:

     • a -> 2

     • b -> 4

     • c -> 2

     • d -> 2

     • e -> 4

Frequency Vector: [4, 4, 2, 2, 2, 2]

2. Sorting Frequencies:

   • After sorting: [4, 4, 2, 2, 2, 2]

3. Calculating Minimum Pushes:

   • Complete groups of 8: 0 (since we have only 6 elements, there are no complete groups)

   • Remaining: 6

Thus, the total number of pushes is 4*1 + 4*1 + 2*1 + 2*1 + 2*1 + 2*1 = 16.

Hence, the minimum number of pushes required to type the word aabbbbccddeeee is 16.

Code

        class Solution {
        public:
            int minimumPushes(string word) {
                map<char,int>fre;
                for(auto it: word){
                    fre[it]++;
                }
                vector<int>res;
                for(auto it: fre){
                    int s=it.second;
                    res.push_back(s);
                }
                sort(res.begin(), res.end(), greater<int>());
                int div=res.size()/8;
                int mod=res.size()%8;
                int k=1, ans=0, last=res.size()-1;
                for(int i=0; i<div; i++){
                   for(int j=(i*8); j<(i+1)*8; j++){
                      ans+=(res[j]*k); 
                   } 
                    ++k;
                }
                while(mod--){
                    ans+=(res[last]*(div+1));
                    last--;
                }
                return ans;
            }
        };

        class Solution:
            def minimumPushes(self, word: str) -> int:
                fre = {}

                # Count the frequency of each character
                for ch in word:
                    if ch in fre:
                        fre[ch] += 1
                    else:
                        fre[ch] = 1

                # Store frequencies in a list
                res = list(fre.values())

                # Sort the frequencies in descending order
                res.sort(reverse=True)

                # Calculate the minimum pushes
                div = len(res) // 8
                mod = len(res) % 8
                k = 1
                ans = 0
                last = len(res) - 1

                for i in range(div):
                    for j in range(i * 8, (i + 1) * 8):
                        ans += res[j] * k
                    k += 1

                while mod > 0:
                    ans += res[last] * (div + 1)
                    last -= 1
                    mod -= 1

                return ans

Submission history:

Thank you and Happy Coding!