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