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.
Example 1:
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:
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:
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 <= 105word consists of lowercase English letters.Approach: The key idea is to map the most frequently occurring letters to keys such that they require fewer presses. By doing this, we can minimize the total number of key presses needed to type the word. First, count the frequency of each character in the word. Then, sort these characters by frequency in descending order. Assign them to the keys with the least number of lever pulls needed - the key with the highest frequency letters receives only one press.
This Python solution uses the Counter class from the collections module to count the frequency of each letter in the word. The frequencies are then sorted in descending order. We process each letter, assigning the most frequent ones to require only one press, using the ((i // 9) + 1) calculation to determine the number of presses for remapped keys.
JavaScript
Time Complexity: O(n + k log k), where n is the length of the word and k is the number of unique letters. Sorting takes O(k log k).
Space Complexity: O(k), where k is the number of unique letters stored in `frequency`.
Approach: Allocate keys dynamically based on frequency but with a twist: instead of pre-sorting all letters, allocate keys to letters in frequency order and determine the number of presses required for each allocation. Keep track of the frequency allocation dynamically using numeric keys to reallocation.
This C solution uses an array to store the frequency of each letter. It then uses the qsort function to sort these frequencies in descending order, emulating a dynamic allocation of key mappings based on increasing frequency pull multipliers.
Java
Time Complexity: O(n + k log k), where n is the size of the word and k is the number of possible unique letters (26).
Space Complexity: O(1), as it uses fixed-size auxiliary space irrespective of input size.
| Approach | Complexity |
|---|---|
| Greedy Frequency Mapping | Time Complexity: O(n + k log k), where n is the length of the word and k is the number of unique letters. Sorting takes O(k log k). |
| Dynamic Key Allocation | Time Complexity: O(n + k log k), where n is the size of the word and k is the number of possible unique letters (26). |
Minimum Number of Pushes to Type Word II - Leetcode 3016 - Python • NeetCodeIO • 9,491 views views
Watch 9 more video solutions →Practice Minimum Number of Pushes to Type Word II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor