⚡Flashcard Drill➔
NeetCode #790LC-3016MediumGreedy
← Back to All Problems

#790 · #3016 · Minimum Number of Pushes to Type Word II(输入单词需要的最少按键次数 II)

📌 Problem Statement & Constraints

You are given a string word. You may remap letters to the eight keys labelled 2 to 9; the cost to type a letter is its position on its key (1-indexed). Return the minimum total pushes to type word. Constraints: 1 <= word.length <= 10^5, word consists of lowercase English letters.

💡 Core Algorithmic Approaches

  1. Each key can hold many letters, but the first letter on a key costs 1 push, the second costs 2, and so on.
  2. Across the eight keys there are 8 slots of cost 1, 8 slots of cost 2, 8 of cost 3, etc.
  3. To minimise the total, assign the most frequent letters to the cheapest slots.
  4. Sort the letter frequencies descending and give the i-th one the cost i // 8 + 1.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumPushes(self, word: str) -> int:
        from collections import Counter
        freq = sorted(Counter(word).values(), reverse=True)
        return sum(f * (i // 8 + 1) for i, f in enumerate(freq))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + 26 log 26): counting plus a small sort.
💾 Space Complexity
O(1): at most 26 frequency entries.

⚠️ Interview Pitfalls & Follow-ups

  • Using 26 keys instead of 8: only keys 2 to 9 exist, so the slot grouping is by 8.
  • Assigning the most frequent letters the largest cost: the ordering must be descending by frequency.
  • Forgetting that a key can hold more than three letters: the cost grows without bound per key.
  • Using the cost i // 8: the first slot must cost 1, not 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems