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

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.