# 3016. Minimum Number of Pushes to Type Word II

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

### Thoughts

* Immediately before I even finished reading I am thinking this may involve a greedy algorithm
    
    * definitely a greedy problem
        
* need to represent the keypad, an array would work
    
* if there are less than 8 unique letters in the word, the obvious solution is to just remap all of the keys to have one of the less than 8 letters
    
    * the harder solution is when there is more than 8 characters that need to be mapped, in this case looking at the character frequency matters (I think) because you don't want to have to make multiple presses for a character you need a lot
        
        * like in example 3: the word is `aabbccddeeffgghhiiiiii`, so obviously you want `i` to be the first letter on a key so that you don't have to double push to get to `i` every time
            
    * I think that the best solution would be to sort the characters by their frequency within the word, and then just remap the keys with those characters in descending order
        
* was stumped for a while, but I think the solution is to disregard what the letters actually are after calculating the frequencies. I was getting too bogged down with trying to associate the specific letters with their specific frequencies, when really the specific letters don't matter, what matters is *a* letter has that frequency
    
    * the solution now seems to be to calculate the frequencies using a map, and then sorting the values in a separate data structure, then iterating through them in descending order to remap the characters
        

### Solution

```java
class Solution {
    public int minimumPushes(String word) {
        HashMap<Character, Integer> map = new HashMap();
        int pushes = 0;

        // Add all characters to the map with their frequencies
        for (char c : word.toCharArray()) {
            map.put(c, (map.containsKey(c) ? map.get(c) + 1 : 1));
        }

        // Sort the frequencies by descending order
        ArrayList<Integer> arr = new ArrayList(map.values());
        Collections.sort(arr, Collections.reverseOrder());

        // Iterate through the frequencies, and sum the pushes
        for (int i = 0; i < arr.size(); i++) {
            int key = (i / 8) + 1;
            pushes += key * arr.get(i);
        }

        return pushes;
    }
}
```

**Time Complexity:** O(n log n)  
**Space Complexity:** O(n)

### Conclusion

This one definitely took me a lot longer than it should have. I got too focused on the individual letters and their frequencies instead of just thinking about the frequencies as a whole. Because the specific frequency of `j` or `q` or `a` doesn't matter, what matters is the frequencies together since this problem is only asking about the **number** of pushes, not exactly how you would remap the keys. I should continue to work on similar problems to this so that I get more used to thinking in the correct way to see the answer.