# Minimum Number of Pushes to Type Word II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-pushes-to-type-word-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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.glich.co/dsa/minimum-number-of-pushes-to-type-word-ii/image0.png) 

**Example 1:**

![](https://assets.glich.co/dsa/minimum-number-of-pushes-to-type-word-ii/image1.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.glich.co/dsa/minimum-number-of-pushes-to-type-word-ii/image2.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.glich.co/dsa/minimum-number-of-pushes-to-type-word-ii/image3.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.

# Approaches
## Greedy Approach with Repeated Maximum Finding
This approach follows a greedy strategy. The core idea is that characters with higher frequencies should be assigned to key positions that require fewer pushes. To minimize the total pushes, we should assign the most frequent character to a 1-push position, the second most frequent to another 1-push position, and so on, until all 8 1-push positions are filled. Then we move to 2-push positions. This approach implements this strategy by repeatedly finding the character with the current maximum frequency and assigning it to the next available cheapest slot.
**Time:** O(N + K^2), where N is the length of the word and K is the number of unique characters. Counting frequencies takes O(N). The main loop runs K times. Inside the loop, finding the maximum frequency takes O(K) and removing an element from an `ArrayList` can also take O(K). This results in an O(K^2) complexity for the assignment part. Since K is at most 26, K^2 is a small constant, so the overall complexity is dominated by O(N). · **Space:** O(K), for the frequency map and the list of frequencies, where K is the number of unique characters. Since K <= 26, this is O(1) constant space.
**Pros:** Conceptually simple greedy logic.; Correctly solves the problem.
**Cons:** The O(K^2) part is less efficient than a sorting-based approach. Repeatedly scanning the list to find the maximum is suboptimal.
### Explanation
First, we count the frequency of each character in the input string `word`. A hash map or an array of size 26 can be used for this. We then extract the frequencies of the unique characters into a list. We loop as many times as there are unique characters. In each iteration, we find the maximum frequency in our list, calculate its contribution to the total pushes, and then remove it from consideration for the next iteration (e.g., by setting its value to 0 or removing it from the list). The cost (number of pushes) for each character is determined by its rank in the sorted frequency order. The first 8 characters get a cost of 1, the next 8 get a cost of 2, and so on. We keep track of how many characters have been assigned to determine the current cost.

```java
import java.util.*;

class Solution {
    public int minimumPushes(String word) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : word.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        List<Integer> frequencies = new ArrayList<>(freqMap.values());
        
        int totalPushes = 0;
        int assignedCount = 0;
        
        while (!frequencies.isEmpty()) {
            int maxFreq = 0;
            int maxIndex = -1;
            
            for (int i = 0; i < frequencies.size(); i++) {
                if (frequencies.get(i) > maxFreq) {
                    maxFreq = frequencies.get(i);
                    maxIndex = i;
                }
            }
            
            int pushes = (assignedCount / 8) + 1;
            totalPushes += maxFreq * pushes;
            
            frequencies.remove(maxIndex);
            assignedCount++;
        }
        
        return totalPushes;
    }
}
```
### Algorithm
*   Create a frequency map (e.g., `HashMap<Character, Integer>`) to store the counts of each character in `word`.
*   Iterate through `word` and populate the frequency map.
*   Create a list containing all the frequency values from the map.
*   Initialize `totalPushes = 0` and `assignedCount = 0`.
*   While the list of frequencies is not empty:
    *   Find the maximum frequency in the list.
    *   Determine the cost for this character. The cost is `(assignedCount / 8) + 1`.
    *   Add `maxFrequency * cost` to `totalPushes`.
    *   Remove the maximum frequency from the list.
    *   Increment `assignedCount`.
*   Return `totalPushes`.

## Greedy Approach with Sorting
This is an optimized version of the greedy strategy. Instead of repeatedly finding the maximum frequency, we can determine the optimal assignment more efficiently. The key insight remains the same: characters with higher frequencies must be assigned to positions with fewer pushes. By sorting all character frequencies in descending order, we can directly map the most frequent characters to the cheapest slots.
**Time:** O(N + K log K), where N is the length of the word and K is the number of unique characters. Counting frequencies takes O(N). Collecting non-zero frequencies takes O(1) (since we iterate through a 26-element array). Sorting the K frequencies takes O(K log K). Calculating the final sum takes O(K). Since K <= 26, K log K is a small constant, so the overall complexity is effectively O(N). · **Space:** O(K), for the frequency array and the list to be sorted, where K is the number of unique characters. Since K <= 26, this is O(1) constant space.
**Pros:** Highly efficient, representing the optimal solution.; The logic is clean and directly implements the greedy strategy.; Using an array for frequency counting is faster than a hash map for this problem.
**Cons:** Requires sorting, which might be slightly more complex to implement from scratch compared to the repeated search, but standard library functions make it trivial.
### Explanation
First, we count the frequency of each character. An array of size 26 is a highly efficient way to do this for lowercase English letters. We then collect all the non-zero frequencies. We sort these frequencies in descending order. This places the characters that appear most often at the beginning of our sorted list. Finally, we iterate through the sorted list of frequencies. The first 8 frequencies correspond to characters that will be assigned to 1-push slots. The next 8 will be assigned to 2-push slots, and so on. The cost for a character at index `i` in the sorted list is `(i / 8) + 1`. We calculate the total pushes by summing up `frequency * cost` for each frequency in the list.

```java
import java.util.*;

class Solution {
    public int minimumPushes(String word) {
        int[] freq = new int[26];
        for (char c : word.toCharArray()) {
            freq[c - 'a']++;
        }

        List<Integer> frequencies = new ArrayList<>();
        for (int f : freq) {
            if (f > 0) {
                frequencies.add(f);
            }
        }

        // Sort frequencies in descending order
        Collections.sort(frequencies, Collections.reverseOrder());

        int totalPushes = 0;
        for (int i = 0; i < frequencies.size(); i++) {
            int f = frequencies.get(i);
            int pushes = (i / 8) + 1;
            totalPushes += f * pushes;
        }

        return totalPushes;
    }
}
```
### Algorithm
*   Create a frequency array `freq` of size 26, initialized to zeros.
*   Iterate through the input `word` and increment the count for each character in the `freq` array (`freq[c - 'a']++`).
*   Create a list to store the non-zero frequencies from the `freq` array.
*   Sort this list of frequencies in descending order.
*   Initialize `totalPushes = 0`.
*   Iterate through the sorted list with index `i` from 0 to `list.size() - 1`:
    *   Get the frequency `f` at index `i`.
    *   The number of pushes for this character is `(i / 8) + 1`.
    *   Add `f * ((i / 8) + 1)` to `totalPushes`.
*   Return `totalPushes`.

# Solutions
### Java

```java
class Solution {
public
  int minimumPushes(String word) {
    int[] cnt = new int[26];
    for (int i = 0; i < word.length(); ++i) {
      ++cnt[word.charAt(i) - 'a'];
    }
    Arrays.sort(cnt);
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
      ans += (i / 8 + 1) * cnt[26 - i - 1];
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function minimumPushes ( word ) { const cnt = Array ( 26 ). fill ( 0 ); for ( const c of word ) { ++ cnt [ c . charCodeAt ( 0 ) - ' a ' . charCodeAt ( 0 )]; } cnt . sort (( a , b ) => b - a ); let ans = 0 ; for ( let i = 0 ; i < 26 ; ++ i ) { ans += ((( i / 8 ) | 0 ) + 1 ) * cnt [ i ]; } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int minimumPushes(string word) {
    vector<int> cnt(26);
    for (char &c : word) {
      ++cnt[c - 'a'];
    }
    sort(cnt.rbegin(), cnt.rend());
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
      ans += (i / 8 + 1) * cnt[i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumPushes(self, word: str) -> int: cnt = Counter(word) ans = 0 for i, x in enumerate(sorted(cnt . values(), reverse=True)): ans += (i // 8 + 1) * x return ans

```