Minimum Number of Pushes to Type Word II — 🟡 Intermediate (2/3) — LeetCode Daily Python Solution (8 letters per key, not 3)

Introduction

Every keypad-based typing problem on LeetCode traces back to the same real-world annoyance: your phone's T9 layout was designed around finger reach, not typing speed. Key 2 permanently owns a, b, c whether or not those letters ever show up in what you're typing. Minimum Number of Pushes to Type Word II flips that constraint on its head — you get to design the keypad yourself, choosing which letters land on which key, with the sole goal of minimizing total key presses for a given word.

This problem shows up in interviews because it tests something more valuable than syntax: can you recognize when a problem is secretly asking for a greedy assignment based on frequency? That pattern — sort by how often something occurs, then hand the cheapest resource to the most common items — powers everything from Huffman coding to cache eviction policies to music app "recently played" shortcuts. If you can spot it here, you'll spot it in a dozen other disguises.

Problem Overview

You're given a lowercase English word and eight keys (keys 2 through 9). You must distribute all 26 letters of the alphabet across these eight keys, with each key holding its own distinct set of letters — no overlaps, no restrictions on how many letters a key can hold.

Typing a letter costs a number of pushes equal to its position on its key. The first letter assigned to a key costs 1 push, the second letter on that same key costs 2 pushes, the third costs 3, and so on.

Given a word, you choose the letter-to-key assignment that minimizes the total number of pushes needed to type the entire word, where each letter's cost is multiplied by how many times it appears.

The word can be up to 100,000 characters long, but since there are only 26 possible letters, the actual "shape" of the problem never grows past that fixed alphabet size.

Example

Take word = "abcde". Every letter appears exactly once. No matter how you distribute them, each one only needs its first slot on some key, so every letter costs exactly 1 push. Total: 5.

Now take word = "aabbc". Frequencies are a: 2, b: 2, c: 1. There are only three distinct letters, so all three easily fit as the first letter on three separate keys — every occurrence costs 1 push. Total: 2 + 2 + 1 = 5.

Notice both examples land on 5, but for very different reasons — one because every letter is unique, the other because even repeated letters stayed cheap since there weren't enough distinct letters to force anyone into a second-tier slot.

Intuition

Start from the failure case: a real phone keypad. Key 2 is stuck with a, b, c forever. If your word is packed with the letter z, you're paying an expensive, rigid price for no reason — z might be your most frequent letter, yet the fixed real-world layout dumps it into a high-cost slot at the very last key while a, b, c sit comfortable and cheap regardless of how rarely they're used.

This problem removes that rigidity. Since you choose the layout, the smart move is obvious once you say it out loud: give the cheapest slots to the letters you'll type most often.

Think of a spice rack. The sauce you reach for daily sits at the front, within arm's reach. The jar you use twice a year goes on the top shelf, out of the way. It costs you nothing extra to organize it this way, and it saves real effort every single day. Music apps do this too — your most-played tracks get one-tap shortcuts, while your neglected playlist requires digging.

Here's the proof this greedy idea actually is optimal, not just intuitive: imagine a frequent letter sitting in a cost-2 slot while a rarer letter sits in a cost-1 slot. Swap them. The frequent letter now costs less per occurrence, the rare letter costs more per occurrence — but since the frequent letter occurs more, the total only drops or stays the same. It never increases. That means any arrangement not sorted by frequency can always be improved, so the fully sorted arrangement must be optimal.

With eight keys and unlimited letters per key, the cost structure falls into clean blocks of eight:

• Ranks 0–7 (the 8 most frequent letters): cost 1 each
• Ranks 8–15 (next 8 most frequent): cost 2 each
• Ranks 16–23 (next 8): cost 3 each
• Ranks 24–25 (the last 2, since there are only 26 letters): cost 4 each

I call this the Frequency Ladder — every group of 8 ranks climbs one rung, and one rung equals one extra push.

Brute Force Solution

Idea: Try every possible way to partition 26 letters across 8 keys, compute the total cost for each partition, and keep the minimum.

Algorithm: Generate all partitions of the alphabet into 8 (possibly empty) groups, assign costs 1, 2, 3... within each group, sum up frequency × cost for every letter in the word, and track the best result.

Advantages: Conceptually simple — it's guaranteed correct because it checks everything.

Disadvantages: The number of ways to partition 26 items into 8 ordered groups is astronomically large. This is completely infeasible to compute directly.

Time complexity: Exponential (technically related to Stirling numbers of the second kind times permutations) — intractable. Space complexity: Also exponential if you tried to enumerate partitions.

Brute force isn't a real option here — it's mentioned only to highlight why the greedy insight matters so much. Once you see the swap argument from the Intuition section, brute force becomes unnecessary.

Optimal Solution

The Frequency Ladder approach runs in four clean steps:

1. Count how often each letter appears in the word.
2. Sort those frequencies in descending order — most common first.
3. Rank each frequency by its position (0-indexed) in that sorted list.
4. Cost each rank as (rank // 8) + 1, multiply by its frequency, and sum everything.

Rank	Key slot	Cost per push
0–7	1st letter on 8 keys	1
8–15	2nd letter on 8 keys	2
16–23	3rd letter on 8 keys	3
24–25	4th letter on 2 keys	4

Walking through a slightly bigger example — 9 distinct letters with sorted frequencies [5, 4, 4, 3, 3, 2, 2, 1, 1]:

• Ranks 0–7 (the first eight letters) each cost 1 push per occurrence: 5+4+4+3+3+2+2+1 = 24
• Rank 8 (the ninth letter) crosses into the second rung, costing 2 pushes per occurrence: 1 × 2 = 2
• Total: 24 + 2 = 26

No heaps, no dynamic programming — just counting, sorting, and integer division.

Python Code

from collections import Counter


def minimum_pushes(word: str) -> int:
    """Return the minimum total key presses to type `word`
    on a keypad we design ourselves (8 keys, letters assigned
    by descending frequency)."""
    frequencies = sorted(Counter(word).values(), reverse=True)

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

    return total_pushes

Code Walkthrough

• Counter(word) performs a single linear pass over the word, producing a dictionary of letter -> frequency.
• .values() pulls out just the frequency counts — we don't need to know which letter they belong to, only how often each occurs.
• sorted(..., reverse=True) orders those counts from most frequent to least frequent. This ordering is what makes the greedy assignment valid.
• enumerate(frequencies) gives us rank, the 0-indexed position of each frequency in the sorted list — this rank stands in for "which slot on which key" without us ever having to model actual keys.
• (rank // 8) + 1 converts rank directly into cost. Ranks 0 through 7 all floor-divide to 0, giving cost 1. Ranks 8 through 15 floor-divide to 1, giving cost 2. And so on.
• freq * cost scales the per-occurrence cost by how many times that letter actually appears in the word, and we accumulate the running total.

Dry Run

Let's trace word = "aabbc" by hand.

1. Counter("aabbc") → {'a': 2, 'b': 2, 'c': 1}
2. .values() → [2, 2, 1]
3. sorted(reverse=True) → [2, 2, 1] (already descending)
4. Enumerate:
   • rank 0, freq 2 → cost 0 // 8 + 1 = 1 → contributes 2 × 1 = 2
   • rank 1, freq 2 → cost 0 // 8 + 1 = 1 → contributes 2 × 1 = 2
   • rank 2, freq 1 → cost 0 // 8 + 1 = 1 → contributes 1 × 1 = 1
5. Total: 2 + 2 + 1 = 5

Matches the expected answer.

Complexity Analysis

Time complexity: O(n), where n is the length of the word. Building the Counter is a single linear scan — O(n). Sorting the frequency values touches at most 26 numbers (one per letter of the alphabet), which is a constant-size sort, effectively O(1) regardless of how large n gets. The final loop over frequencies is also bounded by 26 iterations. So the dominant cost is the initial counting pass, giving overall O(n).

Space complexity: O(1) relative to the alphabet — the Counter and the sorted list can hold at most 26 entries, since there are only 26 lowercase English letters. This stays constant no matter how long the word is.

Alternative Solutions

You could replace the sorted() call with a bucket sort over the 26 possible frequency values (since frequencies are bounded by n, you could bucket them and read off counts in descending order without a comparison sort). This would technically avoid the O(k log k) sort step entirely. In practice, since k is fixed at a maximum of 26, this optimization saves nothing meaningful — sorting 26 numbers is already about as fast as anything gets. Stick with sorted(); it's clearer and just as fast for this input size.

Edge Cases

• Single character word ("a"): only one letter, rank 0, cost 1. Returns 1.
• All identical characters ("aaaa...a"): only one distinct letter, always rank 0, always cost 1. Total equals the word's length.
• All 26 letters used with maximal spread: the two least frequent letters land at ranks 24 and 25, finally reaching cost 4 — the most expensive rung on the ladder.
• Empty word: not a valid input per constraints, but the function would correctly return 0 since Counter("") produces an empty dict.
• Word with exactly 8 distinct letters: every letter fits in the cost-1 tier exactly, with no letter ever paying more than 1 push.

Common Mistakes

1. Sorting frequencies ascending instead of descending — this hands your most frequent letter the most expensive slot, exactly backwards from the greedy proof.
2. Assuming a real T9 keypad layout applies — this problem asks you to design your own layout; the real-world a, b, c on key 2 is irrelevant here.
3. Forgetting to multiply cost by frequency — computing cost per rank but summing costs instead of frequency × cost gives the wrong total.
4. Off-by-one errors in the rank-to-cost formula — using rank // 8 without the + 1 will give cost 0 for the first tier instead of cost 1.
5. Trying to model actual key assignments explicitly — you never need to track which physical key a letter lives on; the rank alone fully determines the cost.

Interview Questions

• Why is sorting by frequency guaranteed to produce the optimal result? (Be ready to explain the swap argument.)
• How would your solution change if there were a different number of keys, or a different alphabet size?
• Could you solve this without sorting, using a counting/bucket approach? What's the tradeoff?
• What's the time complexity if the alphabet size were unbounded instead of fixed at 26?
• How does this problem relate to Huffman coding or other greedy compression techniques?

Similar Problems

• Minimum Number of Pushes to Type Word I — the simpler sibling where letters are ranked by first appearance in the word rather than by frequency; a great next problem to test whether you actually understand why frequency matters here.
• Huffman Encoding — the same "cheap slot for common item, expensive slot for rare item" greedy principle, applied to building optimal prefix codes.
• Top K Frequent Elements — shares the same Counter + sort-by-frequency backbone.
• Reorganize String — another frequency-driven greedy arrangement problem.

Key Takeaways

The moment a problem lets you choose an assignment freely, ask whether frequency should drive that assignment. Count occurrences, sort descending, and let rank determine cost — that's the entire Frequency Ladder pattern. The swap argument is what elevates this from "seems right" to provably optimal, and that kind of reasoning is exactly what separates a solution you can defend in an interview from one you got lucky with.

Watch the Video

For the full walkthrough with the hand-traced "aabbc" example and the two most common mistakes flagged in real time, watch the video here: {LINK}

About the Series

This breakdown is part of Fun with Learning Technology, a series that treats interview problems as excuses to talk about the ideas underneath them — sorting, greedy proofs, frequency analysis, and the intuition that turns a memorized trick into something you can reconstruct from scratch under pressure.

Call To Action

If this clicked for you, drop a like on the video and subscribe on YouTube — it directly helps this channel grow. For deeper written breakdowns like this one delivered straight to your inbox, subscribe to the Substack. And if you spotted a cleaner way to explain the swap argument, or you tried Word I after watching, drop a comment — I read every one.

---

from collections import Counter

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