Minimum Number of Pushes to Type Word II

Map letters to phone keys greedily — most frequent letters get position 1.

Medium
Time O(N + 26 log 26) Space O(1)
LeetCode
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#

Minimum Number of Pushes to Type Word II
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.