Minimum Number of Pushes to Type Word I — 🟡 Intermediate (2/3) — LeetCode Daily Python Solution ('abcdefghi' = 10 pushes)

Introduction

Every so often LeetCode hands you a problem that looks like a keypad puzzle on the surface and turns out to be a classic algorithm in disguise. Minimum Number of Pushes to Type Word I is one of those. It's rated easy-to-medium in difficulty, but the way you arrive at the solution — the reasoning, not the code — is exactly the kind of thinking interviewers at companies like Amazon and Bloomberg are trying to draw out of you.

The code you'll end up writing is short. Genuinely short — a Counter call and a sorted sum. But the interesting part isn't the code, it's the two-minute mental leap that gets you there: realizing that a problem about "assigning letters to keys" is actually a problem about "which positions are scarce." That's the same insight behind Huffman coding, the compression algorithm that shrinks real files by giving common symbols short codes and rare symbols long ones. Once you've internalized this pattern, you'll start recognizing it in problems that don't look anything like this one on the surface.

Problem Overview

You're given a word made entirely of distinct lowercase letters. You have 8 keys on a keypad, and you get to decide, freely, which letters go on which key and in what order within that key.

Typing a letter costs a number of pushes equal to its position on its key. The first letter assigned to any key costs 1 push. The second letter assigned to that same key costs 2 pushes. The third costs 3, and so on. There's no cap on how many letters you can pile onto one key — you could technically put every letter on a single key if you wanted to (you'd just pay heavily for it).

Your job: assign every letter in the word to a key, in some order, so that the total number of pushes needed to type the entire word is as small as possible. Return that minimum total.

Example

Take word = "xycdefghij" — ten distinct letters.

You have 8 keys, so the smartest strategy is to spread the first 8 letters across all 8 keys, one letter per key, each costing 1 push. That covers x, y, c, d, e, f, g, h. Now you have 2 letters left over — i and j — and only 8 keys, all of which already have one letter on them. Those two have to become the second letter on some key, which costs 2 pushes each.

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

Now try word = "abcdefghi" — nine letters. The first 8 (a through h) each land on their own key at 1 push apiece, costing 8. The ninth letter, i, has nowhere cheap left to go — it becomes a second letter on one of the keys, costing 2. Total: 8 + 2 = 10.

Notice something important: in both examples, which letter ends up paying the higher cost didn't matter to the math — only how many letters existed and how they got distributed across buckets of 8.

Intuition

Here's the trap most people fall into on first read: since every letter in the word is distinct, it's tempting to assume the assignment is arbitrary — just spread letters across 8 keys and be done with it. That works fine as long as you have 8 or fewer letters; everyone gets the cheapest slot, one push each, and there's nothing to optimize.

The moment you cross 8 letters, though, a real decision appears. You now have more letters than cheap slots. Someone has to pay 2 pushes instead of 1. The question becomes: who pays it?

Think about a parking lot. The spots closest to the entrance are the most convenient, and there's a limited number of them. You wouldn't give the closest spot to a car that's there once a month and stick the daily commuter's car at the far end. You give the closest spots to the cars that come and go the most. The scarce resource (near spots, or in our case, cheap first-position slots) should go to whoever uses it most.

Translate that back to letters: since this problem doesn't care about the letters' identities — only how often each one appears in the final typed word — the letters that show up most often should get the cheapest positions. Sort letter frequencies from highest to lowest, then greedily hand out the cheap slots first. Once the first 8 slots (cost 1) are full, the next 8 letters have to accept cost 2. Once those are full, the next 8 pay cost 3, and so on.

This is Huffman coding's core idea, just simplified because every letter here occupies exactly one "slot" instead of a variable-length code — put your most-used items where they're cheapest to reach.

Brute Force Solution

Idea: Try every possible way to assign letters to the 8 keys and every possible ordering within each key, compute the total cost for each arrangement, and keep the minimum.

Algorithm:

1. Generate all permutations of letter-to-key-position assignments.
2. For each arrangement, compute total pushes.
3. Track the minimum across all arrangements.

Advantages: Guaranteed correct — it's an exhaustive search, so it can't miss the optimal arrangement.

Disadvantages: The number of arrangements explodes combinatorially. With up to 26 distinct letters, you're looking at something on the order of 26! possible orderings before even accounting for key groupings — completely unusable outside of tiny inputs.

Time complexity: O(n!) — factorial, dominated by the number of ways to order n letters. Space complexity: O(n) for storing a candidate arrangement, though the search space itself is what kills this approach.

Optimal Solution

The greedy approach collapses that entire search space into three steps:

1. Count frequencies. Use a Counter to tally how many times each letter appears in the word.
2. Sort descending. Order those counts from most frequent to least frequent — the busiest letters go first.
3. Bucket by 8, cost rises per bucket. Walk through the sorted counts. The first 8 entries (rank 0–7) belong to bucket 1, costing 1 push each. The next 8 (rank 8–15) belong to bucket 2, costing 2 pushes each. In general, the letter at rank i (0-indexed) belongs to bucket i // 8 + 1.

Rank (0-indexed)	Bucket (rank // 8 + 1)	Cost per push
0–7	1	1
8–15	2	2
16–23	3	3
24–25	4	4

For each letter, multiply its frequency by its bucket number and add that to a running total. That running total is your answer.

Python Code

from collections import Counter


def minimum_pushes(word: str) -> int:
    """Return the minimum key pushes needed to type `word`."""
    frequencies = sorted(Counter(word).values(), reverse=True)

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

    return total_pushes

Code Walkthrough

• Counter(word) builds a dictionary-like tally of how many times each distinct letter appears in word.
• .values() pulls out just the frequency counts, discarding which letter they belong to — we established earlier that identity doesn't matter, only frequency.
• sorted(..., reverse=True) puts the highest frequencies first, so the busiest letters get processed — and priced — first.
• enumerate(frequencies) gives us both the 0-indexed rank and the frequency value as we iterate.
• rank // 8 + 1 computes the bucket number: integer division by 8 groups every 8 consecutive ranks together, and + 1 shifts the cost to start at 1 instead of 0.
• bucket_cost * freq gives the total pushes contributed by this one letter — its per-push cost times how many times it needs typing.
• The running sum, total_pushes, accumulates the answer across all letters.

Dry Run

Walk through word = "abcdefghi":

1. Counter("abcdefghi") → each letter appears once: {'a': 1, 'b': 1, ..., 'i': 1}.
2. .values() sorted descending → [1, 1, 1, 1, 1, 1, 1, 1, 1] (nine 1's — order among equal values doesn't matter).
3. Iterate with rank 0 through 8:
   • Ranks 0–7 (a through h): bucket = 0//8+1 through 7//8+1 = all bucket 1, cost 1 each → contributes 8 × 1 = 8.
   • Rank 8 (i): bucket = 8//8+1 = 1+1 = 2, cost 2 → contributes 1 × 2 = 2.
4. Total = 8 + 2 = 10. ✅ Matches the expected answer.

Complexity Analysis

Time: O(n log n), where n is the number of distinct letters (at most 26). Building the Counter is O(n), but sorting the frequencies dominates at O(n log n). The final loop is O(n).

Space: O(n) for the Counter and the sorted list of frequencies — no extra structures beyond that, and since n is capped at 26, this is effectively constant space in practice.

These bounds are correct because sorting is the only super-linear operation in the whole algorithm, and there's no way to determine bucket assignments without first establishing the frequency ranking.

Alternative Solutions

You could skip building an explicit Counter and instead sort the word's characters directly with a manual frequency pass, but that just re-implements what Counter already does more clumsily. There's no meaningfully different algorithmic alternative here beyond greedy — brute force is correct but exponentially worse, and there's no dynamic programming angle since there's no overlapping subproblem structure to exploit. The greedy sort-and-bucket approach is strictly the right tool.

Edge Cases

• Empty string: No letters to assign, so the total cost is 0.
• Word length ≤ 8: Every letter fits in bucket 1, so the answer is simply the length of the word (or, since letters are distinct, the number of distinct letters).
• Single-letter word: Costs exactly 1 push.
• Exactly 8 letters: All fit at cost 1 each; total equals 8.
• Maximum length (26 distinct letters): Buckets fill up through bucket 4 (ranks 24–25 land in bucket 4), since 26 = 3×8 + 2.

Because the problem guarantees distinct letters, every value from Counter will be exactly 1 — this makes the "sort descending" step trivial (all values are equal), though the bucket logic is what's actually doing the work.

Common Mistakes

1. Forgetting the ranks are 0-indexed and using rank // 8 without checking that rank 7 (the 8th letter) still belongs to bucket 1, not bucket 2.
2. Sorting ascending instead of descending, which would give the rarest letters the cheapest slots — the opposite of what you want.
3. Assuming order doesn't matter for word lengths under 8 and adding unnecessary bucket logic when the answer is just the word's length.
4. Trying to track which specific letter goes where, when the problem only ever asks for a total cost — identity is irrelevant, only frequency and rank matter.
5. Off-by-one errors in bucket cost, forgetting the + 1 and starting costs at 0 instead of 1.
6. Reaching for brute-force permutations out of instinct without recognizing the greedy structure first, leading to a factorial-time solution that times out.

Interview Questions

• How would this change if keys could only hold a fixed maximum number of letters instead of unlimited?
• What if letters weren't guaranteed distinct — how would repeated letters in the input word affect your frequency counting?
• Can you connect this greedy strategy formally to Huffman coding — where do they diverge?
• How would you prove this greedy choice is optimal (an exchange argument)?
• What's the answer if you have k keys instead of a fixed 8?

Similar Problems

• LeetCode 451 — Sort Characters By Frequency: Same core skill — counting and sorting by frequency — applied to string reconstruction instead of cost computation.
• LeetCode 3016 — Minimum Number of Pushes to Type Word II: The direct sequel, where letters can repeat and you need to count occurrences across the whole word rather than treating each letter as appearing once.
• LeetCode 1834 — Single-Threaded CPU: Different domain, same "sort by priority, process greedily" backbone.
• LeetCode 621 — Task Scheduler: Another frequency-driven greedy/bucket problem where the most frequent task dictates the schedule's shape.

Key Takeaways

The lesson here isn't really about keypads — it's about recognizing when a problem's cost structure is scarce and tiered. Whenever you see "limited cheap resources, unlimited expensive ones," count frequencies, sort descending, and hand out the cheap resource to whoever needs it most. That single move turns a factorial brute-force nightmare into an O(n log n) two-liner, and it's a pattern that resurfaces constantly in interview problems well beyond this one.

Watch the Video

Prefer watching this get built step by step, bugs and all? Check out the full walkthrough here: {LINK}

About the Series

This breakdown is part of Fun with Learning Technology, a daily series working through LeetCode's daily challenge in Python — one problem, one clear mental model, every day. The goal isn't just to get a green checkmark, it's to build the kind of pattern recognition that makes the next problem easier too.

Call To Action

If this greedy bucket trick clicked for you, drop a like on the video — it's the easiest way to signal that these breakdowns are worth doing more of. Subscribe on YouTube so tomorrow's daily challenge shows up in your feed, and subscribe to the Substack for the written deep dives like this one delivered straight to your inbox. Got a different way you'd explain the intuition, or a follow-up question an interviewer might throw at you? Drop it in the comments — and if this helped, share it with someone prepping for interviews right now.

---

from collections import Counter

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