Difficulty: 🟢 Easy
Topics: Math, String, Greedy

Solution

LeetCode 3014 - Minimum Number of Pushes to Type Word I

Problem Understanding

We are given a word consisting of distinct lowercase English letters. We are allowed to completely redesign the mapping of letters onto the telephone keypad keys 2 through 9.

There are 8 available keys (2 to 9). Each letter must be assigned to exactly one key, and different keys must contain distinct sets of letters. A key may contain any number of letters.

The cost of typing a letter depends on its position within its assigned key:

The first letter on a key requires 1 push.
The second letter on the same key requires 2 pushes.
The third letter requires 3 pushes.
And so on.

Our goal is to assign the letters in word to the 8 keys so that the total number of key presses required to type the entire word is minimized.

Because all letters in word are distinct, every letter appears exactly once in the word. This significantly simplifies the problem because every letter contributes equally to the final cost. We do not need to consider frequencies.

The input is simply a string word, and the output is the minimum total number of button presses required after choosing the optimal keypad remapping.

The constraints are very small:

1 <= word.length <= 26
All letters are distinct.
Only lowercase English letters appear.

Since there are at most 26 letters, even relatively inefficient solutions would run comfortably. However, the problem has a very elegant greedy solution.

Some important observations and edge cases are:

If the word contains at most 8 letters, each letter can occupy the first position of a different key, so every letter costs 1 press.
When there are more than 8 letters, some letters must occupy second positions and therefore cost 2 presses.
Since all letters occur exactly once, the actual character values do not matter. Only the number of distinct letters matters.
The maximum possible word length is 26, so some letters may need to occupy third or fourth positions on keys.

Approaches

Brute Force

A brute force solution would try every possible assignment of letters to the 8 keys and compute the resulting typing cost.

For each letter, we would decide which key it belongs to and what position it occupies within that key. After constructing a complete mapping, we would calculate the total number of presses and keep the minimum.

This approach is correct because it explores every possible keypad configuration and therefore must eventually find the optimal one.

However, the number of possible assignments grows exponentially with the number of letters. Even with only 26 letters, the search space becomes enormous and completely impractical.

Key Insight

Since every letter appears exactly once, all letters have identical importance.

To minimize the total cost, we should place as many letters as possible into positions that require fewer presses.

There are:

8 positions costing 1 press, one on each key.
8 positions costing 2 presses, one second-position slot on each key.
8 positions costing 3 presses.
And so on.

Therefore:

The first 8 letters should cost 1 press each.
The next 8 letters should cost 2 presses each.
The next 8 letters should cost 3 presses each.
Any remaining letters should cost 4 presses each.

Since only the number of letters matters, we can simply assign costs in groups of 8.

For a letter at index i (0-indexed), its cost is:

$$\left\lfloor \frac{i}{8} \right\rfloor + 1$$

Summing these costs gives the minimum total number of pushes.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible keypad assignments
Optimal	O(n)	O(1)	Assigns letters to cheapest available positions greedily

Algorithm Walkthrough

Let n be the length of word.
Imagine placing the letters into the cheapest available keypad positions.
The first 8 letters occupy the first slot of each key, so each contributes 1 press.
The next 8 letters occupy the second slot of each key, so each contributes 2 presses.
The next 8 letters occupy the third slot of each key, so each contributes 3 presses.
Continue this pattern until all letters have been assigned.
For each letter position i from 0 to n - 1, compute its cost as:

$$\left\lfloor \frac{i}{8} \right\rfloor + 1$$ 8. Add all these costs together and return the result.

Why it works

The keypad provides exactly 8 slots at each press-cost level. Since every letter contributes equally to the total cost, the optimal strategy is always to fill the cheapest available slots first. Any solution that places a letter into a more expensive slot while a cheaper slot remains unused can be improved by swapping assignments. Therefore assigning letters level by level, in groups of 8, produces the minimum possible total cost.

Python Solution

class Solution:
    def minimumPushes(self, word: str) -> int:
        total_pushes = 0

        for i in range(len(word)):
            total_pushes += i // 8 + 1

        return total_pushes

The implementation directly follows the greedy observation.

The variable total_pushes accumulates the answer. We iterate through all letters in the word. Since only the number of letters matters, the actual characters are never used.

For each position i, the expression i // 8 + 1 determines which cost group the letter belongs to. Indices 0 through 7 contribute 1, indices 8 through 15 contribute 2, and so on.

The sum of these costs is returned as the final answer.

Go Solution

func minimumPushes(word string) int {
    totalPushes := 0

    for i := 0; i < len(word); i++ {
        totalPushes += i/8 + 1
    }

    return totalPushes
}

The Go implementation is almost identical to the Python version.

The length of the string determines how many letters must be assigned. Integer division in Go naturally performs floor division, so i/8 + 1 computes the correct cost group. The maximum possible answer is very small, so standard int arithmetic is more than sufficient.

Worked Examples

Example 1

Input:

word = "abcde"

Length = 5.

i	Cost = i//8 + 1	Running Total
0	1	1
1	1	2
2	1	3
3	1	4
4	1	5

Final answer:

Example 2

Input:

word = "xycdefghij"

Length = 10.

i	Cost = i//8 + 1	Running Total
0	1	1
1	1	2
2	1	3
3	1	4
4	1	5
5	1	6
6	1	7
7	1	8
8	2	10
9	2	12

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate through all letters once
Space	O(1)	Only a few variables are used

Since n is the length of the word and each character is processed exactly once, the running time is linear. No additional data structures proportional to the input size are allocated, so the space usage remains constant.

Test Cases

solution = Solution()

assert solution.minimumPushes("abcde") == 5      # Example 1
assert solution.minimumPushes("xycdefghij") == 12  # Example 2

assert solution.minimumPushes("a") == 1          # Single letter
assert solution.minimumPushes("abcdefgh") == 8   # Exactly one full cost-1 group
assert solution.minimumPushes("abcdefghi") == 10 # First letter in cost-2 group

assert solution.minimumPushes("abcdefghijklmnop") == 24  # Two full groups
assert solution.minimumPushes("abcdefghijklmnopq") == 27 # Start of cost-3 group

assert solution.minimumPushes("abcdefghijklmnopqrstuvwx") == 48  # Three full groups

assert solution.minimumPushes("abcdefghijklmnopqrstuvwxyz") == 56  # Maximum length

Test Summary

Test	Why
`"abcde"`	Provided example, fewer than 8 letters
`"xycdefghij"`	Provided example, enters second cost group
`"a"`	Minimum input size
`"abcdefgh"`	Exactly fills all cost-1 slots
`"abcdefghi"`	First letter requiring 2 pushes
`"abcdefghijklmnop"`	Exactly fills two groups
`"abcdefghijklmnopq"`	First letter requiring 3 pushes
`"abcdefghijklmnopqrstuvwx"`	Exactly fills three groups
`"abcdefghijklmnopqrstuvwxyz"`	Maximum constraint size

Edge Cases

Word Length Less Than or Equal to Eight

When the word contains at most eight letters, every letter can be assigned to the first position of a different key. A common mistake is to overcomplicate the assignment process. The implementation naturally handles this because all indices satisfy i // 8 == 0, giving every letter a cost of 1.

Word Length Just Above a Multiple of Eight

Inputs such as "abcdefghi" or "abcdefghijklmnopq" are easy places for off-by-one errors. The ninth letter should cost 2 presses, and the seventeenth letter should cost 3 presses. Using i // 8 + 1 correctly transitions to the next cost level exactly when a group of eight positions has been filled.

Maximum Length of Twenty-Six

The largest possible input uses all distinct lowercase letters. In this case, the cost groups become:

8 letters costing 1
8 letters costing 2
8 letters costing 3
2 letters costing 4

The implementation continues applying the same formula without any special handling, producing the correct minimum total of 56 pushes.