Minimum Number of Pushes to Type Word II

Leetcode Problem:

• Minimum Number of Pushes to Type Word II

Summary

• Given a string of lowercase English letters, find the minimum number of times the keys will be pushed to type the string after remapping the keys on a telephone keypad.

Approach

• The approach used is to first count the frequency of each letter in the string, then sort the letters based on their frequency and map them to the keys in a way that minimizes the number of pushes required.

Complexity

• O(n log n) where n is the number of unique letters in the string

Explain

• The code first counts the frequency of each letter in the string using an array `word_cnt`
• Then it sorts the letters based on their frequency using a merge sort algorithm
• After sorting, it maps the letters to the keys in a way that minimizes the number of pushes required
• The `merge` function is used to merge two sorted subarrays into a single sorted subarray
• The `merge_sort` function is used to recursively sort the letters
• The `minimumPushes` function is the main function that calculates the minimum number of pushes required.

Solution Code:

class Solution {
public:
    int word_cnt[26];
    int sortedAlphabet[26];
    int tmp[26];
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        while(i <= mid && j <= r){
            if(word_cnt[sortedAlphabet[i]] > word_cnt[sortedAlphabet[j]]){
                tmp[cur++] = sortedAlphabet[i++];
            } else {
                tmp[cur++] = sortedAlphabet[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = sortedAlphabet[i++];
        }
        for(i = l; i < cur; i++){
            sortedAlphabet[i] = tmp[i];
        }
    }
    void merge_sort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(l ,mid);
        merge_sort(mid+1, r);
        merge(l, mid, r);
    }
    int minimumPushes(string word) {
        int min_cnt = 0;
        for(int i = 0 ; i < word.size(); i++){
            word_cnt[word[i] - 'a']++;
        }
        for(int i = 0 ; i < 26; i++){
            sortedAlphabet[i] = i;
        }
        merge_sort(0, 25);
        int buttonCnt = 0;
        int ans = 0;
        for(int i = 0 ; i < 26; i++){
            int c = sortedAlphabet[i];
            if (word_cnt[c] == 0) break;
            int click_cnt = buttonCnt / 8 + 1;
            ans += click_cnt*word_cnt[c];
            buttonCnt++;
        }
        return ans;
    }
};