#3014

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Number of Pushes to Type Word I

Calculate the minimum pushes to type a word using a remapped telephone keypad with greedy allocation of letters.

Problem Statement

You are given a string word of distinct lowercase letters. You need to type this word on a telephone keypad where each key maps to a collection of letters. Each press of a key types one letter, and keys can be remapped to any distinct letters.

Keys are numbered 2 to 9, and each key can hold multiple letters. You must remap the keys so that typing the given word uses the fewest total key presses possible. Compute the minimum number of presses needed to type the word under any valid key mapping.

Examples

Example 1

Input: word = "abcde"

Output: 5

The remapped keypad given in the image provides the minimum cost. "a" -> one push on key 2 "b" -> one push on key 3 "c" -> one push on key 4 "d" -> one push on key 5 "e" -> one push on key 6 Total cost is 1 + 1 + 1 + 1 + 1 = 5. It can be shown that no other mapping can provide a lower cost.

Example 2

Input: word = "xycdefghij"

Output: 12

The remapped keypad given in the image provides the minimum cost. "x" -> one push on key 2 "y" -> two pushes on key 2 "c" -> one push on key 3 "d" -> two pushes on key 3 "e" -> one push on key 4 "f" -> one push on key 5 "g" -> one push on key 6 "h" -> one push on key 7 "i" -> one push on key 8 "j" -> one push on key 9 Total cost is 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12. It can be shown that no other mapping can provide a lower cost.

Constraints

1 <= word.length <= 26
word consists of lowercase English letters.
All letters in word are distinct.

Solution Approach

Sort letters by frequency or cost

Count how many times each letter would ideally appear in one push and sort them to prioritize letters that reduce total presses.

Greedy allocation to keys

Assign letters to keys sequentially: fill each key with up to 8 letters per push level, ensuring that earlier letters require fewer pushes to minimize total presses.

Calculate total presses

For each letter in the word, determine its position on the key and sum up the presses. Verify the mapping maintains one-to-one letter-key correspondence to satisfy the problem invariant.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting letters and O(n) for allocation and calculation, giving overall O(n log n). Space complexity is O(n) for storing letter counts and key mappings.

What Interviewers Usually Probe

Candidate immediately suggests a greedy allocation based on letter positions.
Mentions invariant that each letter must map to exactly one key.
Calculates total presses incrementally to check minimal mapping correctness.

Common Pitfalls or Variants

Common pitfalls

Forgetting that each key can hold multiple letters and miscounting pushes.
Assigning letters without respecting one-to-one key-letter mapping.
Assuming sequential key mapping without sorting or prioritizing letter positions.

Follow-up variants

Minimize pushes when some keys have fixed letters and cannot be remapped.
Consider words with repeated letters, adjusting greedy allocation accordingly.
Use weighted letters where some letters cost more per press, adapting the greedy strategy.

FAQ

What is the Minimum Number of Pushes to Type Word I problem about?

It asks for the minimum number of key presses to type a distinct-letter word on a remappable keypad using an optimal allocation.

Which pattern is used in solving this problem?

The solution relies on a greedy choice plus invariant validation pattern to assign letters to keys efficiently.

Can keys be assigned multiple letters?

Yes, each key can hold multiple letters, and the greedy strategy ensures the least total presses.

What happens if letters are not mapped greedily?

Non-greedy mapping can lead to higher total key presses because earlier letters may require extra pushes unnecessarily.

How does GhostInterview approach this problem?

GhostInterview guides step-by-step greedy allocation, calculates total presses, and checks that each letter maps to exactly one key.

terminal

Solution

Solution 1: Greedy Algorithm

We notice that all the letters in the string $word$ are different. Therefore, we can greedily distribute the letters evenly across the $8$ keys to minimize the number of key presses.

1

2

3

4

5

6

7

8

9

class Solution:
    def minimumPushes(self, word: str) -> int:
        n = len(word)
        ans, k = 0, 1
        for _ in range(n // 8):
            ans += k * 8
            k += 1
        ans += k * (n % 8)
        return ans

Continue Practicing

#2864 maximum odd binary number #2844 minimum operations to make a special number #2842 count k subsequences of a string with maximum beauty