Minimum Number of Pushes to Type Word II
Map letters to phone keys greedily — most frequent letters get position 1.
3 min read
hash-map greedy sorting
Problem#
You can program 8 keys of a phone. Each key holds up to 4 letters; pressing a key once gives the first letter, twice the second, etc. Given a string word, return the minimum number of presses to type it if you optimally assign letters to keys.
Examples#
word = "abcde"→5(each letter on its own key, 1 press each).word = "xyzxyzxyzxyz"→12(each letter 4 times, all in slot-1 positions).word = "aabbccddeeffgghhiiiiii"→24.
Constraints#
1 <= word.length <= 10^5, lowercase letters.
Hints#
Hint
Count letter frequencies, sort descending. Top 8 letters take 1 press each; next 8 take 2; next 8 take 3; final 2 take 4.
Approach#
Count letter frequencies. Sort descending. The k-th most frequent letter (0-indexed) costs (k / 8) + 1 presses per occurrence. Sum cnt[k] * (k/8 + 1).
Solution#
class Solution {public: int minimumPushes(string word) { int cnt[26] = {0}; for (char c : word) ++cnt[c - 'a']; vector<int> v(cnt, cnt + 26); sort(v.rbegin(), v.rend()); int ans = 0; for (int i = 0; i < 26; ++i) ans += v[i] * (i / 8 + 1); return ans; }};func minimumPushes(word string) int { cnt := [26]int{} for i := 0; i < len(word); i++ { cnt[word[i]-'a']++ } v := cnt[:] sort.Sort(sort.Reverse(sort.IntSlice(v))) ans := 0 for i := 0; i < 26; i++ { ans += v[i] * (i/8 + 1) } return ans}from collections import Counter
class Solution: def minimumPushes(self, word: str) -> int: cnt = Counter(word) v = sorted(cnt.values(), reverse=True) ans = 0 for i, c in enumerate(v): ans += c * (i // 8 + 1) return ansfunction minimumPushes(word) { const cnt = new Array(26).fill(0); for (let i = 0; i < word.length; i++) cnt[word.charCodeAt(i) - 97]++; cnt.sort((a, b) => b - a); let ans = 0; for (let i = 0; i < 26; i++) ans += cnt[i] * (Math.floor(i / 8) + 1); return ans;}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']++; Integer[] v = new Integer[26]; for (int i = 0; i < 26; i++) v[i] = cnt[i]; Arrays.sort(v, (a, b) -> b - a); int ans = 0; for (int i = 0; i < 26; i++) ans += v[i] * (i / 8 + 1); return ans; }}function minimumPushes(word: string): number { const cnt: number[] = new Array(26).fill(0); for (let i = 0; i < word.length; i++) cnt[word.charCodeAt(i) - 97]++; cnt.sort((a, b) => b - a); let ans = 0; for (let i = 0; i < 26; i++) ans += cnt[i] * (Math.floor(i / 8) + 1); return ans;}Editorial#
The greedy is optimal because press counts grow in lockstep with slot positions (1, 2, 3, 4 repeating). Assigning the most frequent letter to the cheapest slot minimizes the total. Sorting 26 elements is trivial; the dominant cost is the initial linear count pass.
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#