Minimum Number of Pushes to Type Word II

medium greedy sorting counting

Problem

A phone keypad has 8 usable keys (numbered 2–9). You may remap each key to any group of distinct letters; every letter goes on exactly one key. The 1st letter on a key costs 1 push, the 2nd costs 2 pushes, the 3rd costs 3, and so on. Return the minimum total number of key pushes needed to type word after the best remapping.

Inputword = "aabbccddeeffgghhiiiiii"

Output24

9 distinct letters. The 8 most frequent get a 1-push slot; the 9th (“h”, with 2 occurrences) spills into a 2-push slot: 2×1 + 2×1 + 2×1 + 2×1 + 2×1 + 2×1 + 2×1 + 6×1 + 2×2 = 24.

word (lowercase letters)

def minimumPushes(word):
    counts = [0] * 26                       # frequency of each letter
    for ch in word:
        counts[ord(ch) - ord('a')] += 1
    counts.sort(reverse=True)               # most frequent first
    total = 0
    for i, f in enumerate(counts):
        if f == 0:
            break                           # unused letters cost nothing
        total += f * (i // 8 + 1)           # 8 keys per push-tier
    return total

function minimumPushes(word) {
  const counts = new Array(26).fill(0);     // frequency of each letter
  for (const ch of word) counts[ch.charCodeAt(0) - 97]++;
  counts.sort((a, b) => b - a);             // most frequent first
  let total = 0;
  for (let i = 0; i < 26; i++) {
    if (counts[i] === 0) break;             // unused letters cost nothing
    total += counts[i] * ((i / 8 | 0) + 1); // 8 keys per push-tier
  }
  return total;
}

int minimumPushes(String word) {
    int[] counts = new int[26];             // frequency of each letter
    for (char ch : word.toCharArray()) counts[ch - 'a']++;
    Arrays.sort(counts);                    // ascending, so read from the end
    int total = 0, rank = 0;
    for (int i = 25; i >= 0; i--) {
        if (counts[i] == 0) break;          // unused letters cost nothing
        total += counts[i] * (rank / 8 + 1);// 8 keys per push-tier
        rank++;
    }
    return total;
}

int minimumPushes(string word) {
    vector<int> counts(26, 0);              // frequency of each letter
    for (char ch : word) counts[ch - 'a']++;
    sort(counts.rbegin(), counts.rend());   // most frequent first
    int total = 0;
    for (int i = 0; i < 26; i++) {
        if (counts[i] == 0) break;          // unused letters cost nothing
        total += counts[i] * (i / 8 + 1);   // 8 keys per push-tier
    }
    return total;
}

Explanation

Only the frequency of each distinct letter matters, not where it sits in the word. If a letter occurs f times and we place it as the j-th letter on some key (so it costs j pushes each time), its contribution is f × j. We want to minimize the sum.

There are 8 usable keys (2–9). We have 8 “1-push” slots (the first position on every key), then 8 “2-push” slots, then 8 “3-push” slots, and so on. To minimize the total, the letters with the highest frequency should take the cheapest slots.

So the recipe is: count letter frequencies, sort them in non-increasing order, then assign greedily. The letter at sorted index i (0-based) lands in push-tier i / 8 + 1 — indices 0–7 cost 1 push each, 8–15 cost 2, 16–23 cost 3.

The answer is ∑ f_i × (i / 8 + 1) over all letters that actually appear. A simple exchange argument proves greedy is optimal: swapping a higher-frequency letter into a cheaper slot than a lower-frequency one never increases the total.

Example: "aabbccddeeffgghhiiiiii" has frequencies i=6, then eight letters with 2. Sorted: [6,2,2,2,2,2,2,2,2]. The first eight (indices 0–7) cost 1 push; the ninth (index 8, an h with 2 occurrences) costs 2. Total = 6 + 2×7 + 2×2 = 24.

Time: O(n + 26 log 26) = O(n) Space: O(1) (fixed 26-letter table)