Minimum Number of Pushes to Type Word I — 🔴 Advanced (3/3) — LeetCode Daily Python Solution (10 letters, one formula)

Introduction

Every so often LeetCode drops a problem that looks like a throwaway string puzzle but is secretly testing whether you understand one of the most important ideas in algorithm design: greedy optimality through an exchange argument. Minimum Number of Pushes to Type Word I is exactly that kind of problem.

On the surface, it's about an old-style phone keypad — the kind where each number key holds several letters, and you press a key repeatedly to cycle to the letter you want. But the real question the interviewer is asking has nothing to do with phones. It's: given the freedom to assign items to groups, and a cost that depends only on an item's position within its group, how do you minimize total cost?

That shape shows up constantly. It's the backbone of Huffman coding, it appears in load-balancing and task-scheduling problems, and it's a favorite way for interviewers to check whether you can prove a greedy strategy works instead of just guessing that it does. If you can walk through this problem cleanly — including why sorting is the right move — you're demonstrating exactly the kind of reasoning interviewers are trying to find.

Problem Overview

You're given a string made up of lowercase English letters. You want to type this string on a keypad where you get to decide, ahead of time, how letters are distributed across 8 keys. Each key can hold at most 8 distinct letters.

To type a letter, you press its key as many times as its position within that key's group. If a key holds the letters a, b, c in that order, typing a costs 1 press, b costs 2 presses, and c costs 3 presses.

You control the entire assignment: which letters go on which key, and in what order within each key. Your goal is to minimize the total number of key presses needed to type every letter in the word (counting each letter once per distinct occurrence... more precisely, weighted by how often it appears).

The twist in the "I" version of this problem: the word consists of distinct letters only — no repeats. That constraint quietly removes a variable from the problem, and noticing that is half the battle.

Example

Take the word "xycdefghij" — 10 distinct letters, no repeats.

Since every letter appears exactly once, frequency can't distinguish between them. All 10 letters are "equally important," so there's nothing to sort by value. The only thing that matters is how you group them.

With 8 letters allowed per key:

• Put any 8 of the letters on separate keys, one letter each in position 1. Each costs 1 press.
• The remaining 2 letters must share a key with something, landing in position 2. Each costs 2 presses.

Total cost: 8 × 1 + 2 × 2 = 8 + 4 = 12.

That's it — 12 presses to type all 10 letters, regardless of which specific letters end up in which bucket, because they're all weighted equally (each appears once).

Intuition

Here's how an experienced engineer approaches this rather than jumping straight to code.

First, recognize the shape: cost depends on rank, not identity. You've seen this before if you've done Huffman coding or any weighted-scheduling problem — when items get assigned to slots and the slot determines cost, the way to minimize total cost is to put your heaviest (most frequent) items in your cheapest slots.

This is the rearrangement inequality in action: pair descending frequency with ascending cost. If you ever have a scenario where a higher-frequency letter sits in a more expensive slot than a lower-frequency letter, you can swap them and strictly reduce total cost. That swap argument is exactly the "exchange argument" used to prove Huffman coding optimal — and it transfers here without modification.

Now apply the constraint of this specific problem: all letters are distinct, meaning every letter has an implicit frequency of 1. If every item has identical weight, sorting by frequency does nothing — there's no inversion to fix. The exchange argument's conclusion ("sort descending by frequency") degenerates into "any order is equally optimal," because there's nothing to differentiate the items.

What's left? Only the structure of the buckets. With 8 slots per key, the first 8 letters (by rank, in any order since they're tied) go into position 1, the next 8 go into position 2, and so on. This gives you a formula purely from position:

cost(rank) = floor(rank / 8) + 1

This is base-8 digit extraction — if you've worked on radix-adjacent problems, this pattern should feel immediately familiar. Ranks 0–7 cost 1, ranks 8–15 cost 2, ranks 16–23 cost 3, and so on.

For our 10-letter example: ranks 0 through 7 (8 letters) cost floor(7/8)+1 = 1. Ranks 8 and 9 (2 letters) cost floor(8/8)+1 = 2 and floor(9/8)+1 = 2. That reproduces 8×1 + 2×2 = 12.

Brute Force Solution

Idea: Try every possible way of partitioning the letters into groups of at most 8, and every internal ordering within each group, computing total cost for each arrangement, then keep the minimum.

Algorithm:

1. Generate every possible assignment of letters to 8 keys, respecting the 8-letters-per-key cap.
2. For each assignment, order letters within each key in every possible way.
3. Compute the total press cost for that arrangement.
4. Track the minimum cost seen.

Advantages: Conceptually simple, guaranteed correct, no need to reason about optimality.

Disadvantages: Catastrophically slow. With up to 26 distinct letters, the number of ways to partition and order them explodes combinatorially — worst case is on the order of O(26!), which is intractable past roughly a dozen letters. It's not "slow," it's not something you would ever run.

Complexity: Time O(n!) in the worst case, space equally unreasonable for tracking partial states. Worth mentioning to an interviewer only to immediately pivot to why it's unnecessary — brute force isn't a real option here, and knowing that is more valuable than attempting it.

Optimal Solution

The optimal approach follows directly from the intuition above, and it generalizes cleanly to the version of this problem where letters can repeat (LeetCode's "II" variant), which is worth internalizing since interviewers love asking the follow-up.

General version (letters may repeat):

1. Count the frequency of every letter using a Counter.
2. Sort the frequencies in descending order.
3. Assign the most frequent letter to the cheapest available slot, the next most frequent to the next cheapest, and so on — filling 8 slots at "cost 1," then 8 at "cost 2," etc.
4. Sum frequency[i] * (i // 8 + 1) across all letters, where i is the 0-indexed rank after sorting.

Distinct-letters version (this problem): Since every frequency is exactly 1, the sort step does nothing meaningful — it's degenerate. You skip straight to bucketing by rank:

cost(rank) = rank // 8 + 1

Sum that over all ranks from 0 to n - 1.

Rank range	Press cost	Letters covered
0–7	1	up to 8
8–15	2	next 8
16–23	3	next 8
24–25	4	remaining (max 26 letters)

Notice the formula needs no special-casing for small inputs. If n ≤ 8, every rank falls into bucket 0, cost is 1 for each letter, and total cost is simply n. The formula degrades gracefully — that's a correctness signal worth stating out loud in an interview, not just something you happen to notice.

The general (non-distinct) formula also generalizes across key count. Swap the hardcoded 8 for a variable k, and the formula becomes floor(i / k) + 1. Nothing else about the algorithm changes.

Python Code

from collections import Counter


def minimum_pushes(word: str) -> int:
    """Minimum key presses to type `word` on an 8-key keypad,
    given free assignment of letters to keys."""
    frequencies = sorted(Counter(word).values(), reverse=True)

    total_presses = 0
    for rank, freq in enumerate(frequencies):
        cost_per_press = rank // 8 + 1
        total_presses += freq * cost_per_press

    return total_presses


def minimum_pushes_k_keys(word: str, k: int) -> int:
    """Generalized version: assign letters across `k` keys instead of 8."""
    frequencies = sorted(Counter(word).values(), reverse=True)

    total_presses = 0
    for rank, freq in enumerate(frequencies):
        cost_per_press = rank // k + 1
        total_presses += freq * cost_per_press

    return total_presses

Code Walkthrough

• Counter(word) builds a frequency map of every letter in the word in a single pass — O(n).
• .values() pulls just the frequency counts; we don't need to know which letter is which, only how often each one shows up.
• sorted(..., reverse=True) orders frequencies from highest to lowest. This is the step that implements the exchange argument: the most frequent letters get processed first, so they land in the cheapest buckets.
• enumerate(frequencies) gives us the 0-indexed rank of each frequency after sorting.
• rank // 8 + 1 computes which bucket this rank falls into and converts it to a 1-indexed press cost.
• freq * cost_per_press is the total contribution of this letter to the overall press count — how many times it appears, multiplied by what it costs to type it once.
• Summing across all letters gives the final answer.

Note that this code never checks whether letters repeat. It's already correct for the general (non-distinct) case, and — since a frequency of exactly 1 is just a special case — it's correct for the distinct-letters version too, without any extra logic.

Dry Run

Word: "xycdefghij" (10 distinct letters).

1. Counter(word) → each letter maps to frequency 1: {x:1, y:1, c:1, d:1, e:1, f:1, g:1, h:1, i:1, j:1}.
2. .values() → [1, 1, 1, 1, 1, 1, 1, 1, 1, 1].
3. sorted(..., reverse=True) → order doesn't change anything since all values are equal: still ten 1's.
4. Iterate with enumerate:
   • Ranks 0–7 → cost = rank // 8 + 1 = 1. Each contributes 1 * 1 = 1. Subtotal: 8.
   • Ranks 8–9 → cost = rank // 8 + 1 = 2. Each contributes 1 * 2 = 2. Subtotal: 4.
5. Total: 8 + 4 = 12.

Matches the hand-derived answer exactly.

Complexity Analysis

Time: O(n log n), dominated entirely by the sort. Building the Counter is O(n), and the final summation loop is O(n). This is tight — you can't beat comparison-sort-equivalent work here without exploiting more structure than "distinct letters" gives you. Counting sort doesn't help either, since in the distinct-letters case every frequency is 0 or 1, which gives you no useful bucketing signal to exploit.

Space: O(n) for the Counter and the sorted list of frequencies (bounded by the alphabet size, so effectively O(1) in practice for lowercase English letters — at most 26 entries).

Why these are correct: The exchange argument guarantees that sorted-greedy assignment is optimal, not just a reasonable heuristic. Any deviation from descending-frequency-to-ascending-cost pairing can be strictly improved by swapping, so the sorted arrangement is a genuine global minimum, not a local one.

Alternative Solutions

You can replace the explicit loop with a one-line sum() and enumerate:

def minimum_pushes(word: str) -> int:
    frequencies = sorted(Counter(word).values(), reverse=True)
    return sum(freq * (rank // 8 + 1) for rank, freq in enumerate(frequencies))

This isn't asymptotically different — same O(n log n) time — it's purely a style choice. Some interviewers will ask for this compressed form to check comfort with generator expressions; either version is acceptable to present first.

Edge Cases

• Empty string: No letters to type, so the answer is 0. Counter("") returns an empty counter, and the loop simply never executes.
• Fewer than 8 distinct letters: Every letter lands in bucket 0 (cost 1), so total cost is just the number of letters. The formula requires no special-casing to handle this correctly.
• Exactly 8 letters: All costs are 1; total is exactly n. This is the boundary where the formula transitions from "single bucket" to "needs a second bucket."
• Maximum alphabet size (26 distinct letters): Spans buckets of cost 1, 2, 3, and 4. Confirm your loop handles the full range without an off-by-one.
• All letters identical (in the non-distinct variant): Frequency map has a single entry with a large count; that single letter gets rank 0, cost 1, so total cost equals its frequency.

Common Mistakes

1. Forgetting the 1-indexing of press cost. The first letter in a bucket costs 1 press, not 0 — an off-by-one here silently shifts every answer.
2. Sorting ascending instead of descending. This inverts the entire strategy and puts your most "expensive-to-place" letters in the cheapest slots — the exact opposite of optimal.
3. Assuming frequency doesn't matter because letters are distinct. Frequency was never irrelevant in principle — it's just that with all frequencies equal to 1, the sort step becomes a no-op. Missing this distinction leads to reasoning that breaks the moment repeats are allowed.
4. Hardcoding 8 everywhere instead of treating it as a parameter. This makes the natural "what if k keys instead of 8" follow-up much harder to answer cleanly on the fly.
5. Attempting to brute-force the assignment "just to be safe." For any alphabet-sized input this doesn't finish in a reasonable time, and offering it as a real candidate signals you haven't recognized the greedy structure.
6. Not testing the boundary at exactly n = 8 or n = 16, where the bucket transitions happen — these are exactly where off-by-one errors surface.

Interview Questions

• "How would you prove that the greedy sorted assignment is optimal?" — Walk through the exchange/rearrangement argument: any inversion between frequency order and cost order can be swapped for a strict improvement.
• "What changes if there are k keys instead of 8?" — Replace 8 with k in the formula; the rest of the algorithm is unchanged.
• "What if letters can repeat?" — Nothing changes in the code; the Counter-based solution already handles it, since it never assumes frequency equals 1.
• "Can you do better than O(n log n)?" — No, not without more structure than distinct/near-uniform frequencies provide; the sort is unavoidable in general.
• "What's the actual time complexity if the alphabet is small (bounded by 26)?" — Effectively O(1), since the input size to the sort is capped by the alphabet size regardless of the word's length.

Similar Problems

• Huffman Coding — the canonical example of the exact same exchange-argument proof technique applied to prefix-free binary codes.
• Task Scheduler (LeetCode 621) — another problem where frequency-based greedy bucketing determines the optimal schedule length.
• Reorganize String (LeetCode 767) — frequency counting plus greedy placement to satisfy an adjacency constraint.
• Minimum Number of Pushes to Type Word II (LeetCode) — the direct generalization of this problem to repeated letters, solved by the exact same code shown above.
• Rearrange Array to Maximize Prefix Score / similar rearrangement-inequality problems — share the "sort and pair" optimality proof structure.

Key Takeaways

• Whenever cost is a function of an item's rank within a group, think sort-and-bucket — this single idea underlies Huffman coding, scheduling, and this problem.
• The exchange argument isn't just a way to justify a greedy solution intuitively — it's a rigorous proof that no other arrangement can beat it.
• Distinct letters don't remove frequency from the problem; they make every frequency equal, which degenerates the sort step into a formality.
• A well-designed formula, like rank // k + 1, should require no special-casing for small inputs — that's a sign you've found the right abstraction.
• Brute force is worth naming to preempt the question, but never worth attempting; recognizing why it's intractable is itself a signal of strong problem-solving.

Watch the Video

For the full worked walkthrough — including the live derivation of the bucketing formula, the k-key generalization, and a quick quiz to test your understanding — watch the video here: {LINK}

About the Series

This breakdown is part of the Fun with Learning Technology series, where each episode takes a LeetCode problem and dissects the reasoning an experienced engineer actually uses to solve it — not just the final code, but the pattern-recognition and proof techniques that make the solution obvious in hindsight. The goal is to build durable intuition that transfers across problems, not just memorized solutions to individual questions.

Call To Action

If this breakdown helped clarify the greedy exchange argument, consider liking the video on YouTube and subscribing for more daily LeetCode walkthroughs. For deeper dives and written companions to every video, subscribe to the Substack newsletter. Drop a comment with your answer to the quiz round, and share this with anyone prepping for coding interviews.

---

from collections import Counter

def minimumPushes(word: str) -> int:
    freq = Counter(word)
    counts = sorted(freq.values(), reverse=True)