Minimum Number of Pushes to Type Word II
Source: leetcode
Difficulty: Medium
Tags: hash-table, string, greedy, sorting, counting

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.


![](https://assets.leetcode.com/uploads/2023/12/26/keypaddesc.png)
 


**Example 1:**


![](https://assets.leetcode.com/uploads/2023/12/26/keypadv1e1.png)

```

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:**


![](https://assets.leetcode.com/uploads/2024/08/20/edited.png)

```

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:**


![](https://assets.leetcode.com/uploads/2023/12/27/keypadv2.png)

```

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




C++ solution:
struct Solution {
    int minimumPushes(string_view input) {
        int i = 0;
        int j;

        array<int, 26> data;
        for (const char c : input)
            if (96 < c && c < 123)
                ++data[c - 'a'];

        const int SIZE = *max_element(data.begin(), data.end()) + 1;
        int countingSort[SIZE];
        while (i < SIZE)
            countingSort[i++] = 0;
        for (const int n : data)
            ++countingSort[n];

        int k = data.size();
        for (i = 0; i < SIZE; ++i) {
            for (j = 0; j < countingSort[i]; ++j)
                data[--k] = i;
        }

        i = 0;
        j = 8;
        for (const int n : data)
            i += (j++ / 8) * n;
        return i;

        return 0;
    }
};

int init = [] {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ofstream out("user.out");
    cout.rdbuf(out.rdbuf());

    Solution s;
    for (string line; getline(cin, line); cout << endl)
        cout << s.minimumPushes(line);

    exit(0);
    return 0;
}();

Go solution:
func minimumPushes(word string) int {
    letterFreq := make([]int, 26)
    for _, c := range word {
        letterFreq[c - 'a']++
    }
    
    sort.Sort(sort.Reverse(sort.IntSlice(letterFreq)))
    
    totalPresses := 0
    for i, freq := range letterFreq {
        if freq == 0 {
            break
        }
        totalPresses += (i / 8 + 1) * freq
    }
    
    return totalPresses
}

Java solution:
class Solution {
    public int minimumPushes(String word) {
        int[] letterFrequency = new int[26];
        for (char c : word.toCharArray()) {
            letterFrequency[c - 'a']++;
        }
        
        Integer[] sortedFreq = new Integer[26];
        for (int i = 0; i < 26; i++) {
            sortedFreq[i] = letterFrequency[i];
        }
        Arrays.sort(sortedFreq, Collections.reverseOrder());
        
        int totalPresses = 0;
        for (int i = 0; i < 26; i++) {
            if (sortedFreq[i] == 0) break;
            totalPresses += (i / 8 + 1) * sortedFreq[i];
        }
        
        return totalPresses;
    }
}

JavaScript solution:
/**
 * @param {string} word
 * @return {number}
 */
var minimumPushes = function(word) {
    const letterFreq = new Array(26).fill(0);
    for (let c of word) {
        letterFreq[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    letterFreq.sort((a, b) => b - a);
    
    let totalPresses = 0;
    for (let i = 0; i < 26; i++) {
        if (letterFreq[i] === 0) break;
        totalPresses += Math.floor(i / 8 + 1) * letterFreq[i];
    }
    
    return totalPresses;
};

Python solution:
class Solution:
    def minimumPushes(self, word: str) -> int:
        l=[0]*(32)
        for i in range(26):
            l[i]=word.count(chr(97+i))
        l.sort(reverse=True)
        res=0
        for i in range(4):
            for j in range(8):
                res+=(i+1)*l[8*i+j]
        return res

Ruby solution:
# @param {String} word
# @return {Integer}
def minimum_pushes(word)
        freq = Array.new(26) { Array.new(2, 0) }
        (0..25).each do |i|
            freq[i][1] = i
        end
        (0...word.length).each do |i|
            ch = word[i].ord - 'a'.ord
            freq[ch][0] += 1
        end
        
        freq.sort! { |a, b|
            if a[0] == b[0]
                a[1] <=> b[1]
            else
                b[0] <=> a[0]
            end
        }
        
        m = {}
        (0..25).each do |i|
            if freq[i][0] <= 0
                next
            end
            if i < 8
                ch = freq[i][1]
                m[ch] = 1
            elsif i < 16
                ch = freq[i][1]
                m[ch] = 2
            elsif i < 24
                ch = freq[i][1]
                m[ch] = 3
            elsif i >= 24
                ch = freq[i][1]
                m[ch] = 4
            end
        end
        ans = 0
        
        (0...word.length).each do |i|
            c = word[i].ord - 'a'.ord
            if m.key?(c)
                ans += m[c]
            end
        end
        return ans 
end