LeetCode Problem 3016

Difficulty: 🟡 Medium
Topics: Hash Table, String, Greedy, Sorting, Counting

Solution

LeetCode 3016 - Minimum Number of Pushes to Type Word II

Problem Understanding

This problem asks us to redesign a telephone keypad so that typing a given word requires the fewest total key presses possible.

A traditional telephone keypad contains keys 2 through 9, giving us exactly 8 available keys. Each lowercase English letter must be assigned to exactly one of these keys. The assignment is completely flexible. A key may contain any number of letters, and some keys may even remain unused.

Within a key, the position of a letter determines how many presses are required to type it. The first letter assigned to a key costs 1 press, the second costs 2 presses, the third costs 3 presses, and so on.

The input is a string word. We want to choose an optimal mapping of letters to keys so that typing every character in word requires the minimum possible total number of key presses.

The constraints are important:

• 1 <= word.length <= 100000
• Only lowercase English letters appear.
• There are at most 26 distinct letters.

Although the word can be very long, the alphabet size is fixed at 26. This strongly suggests that frequency counting will be useful, because the number of unique characters remains very small.

Some important observations and edge cases:

• A word may contain only one distinct letter.
• A word may contain all 26 letters.
• Some letters may appear many times while others appear only once.
• Since there are only 8 keys, at most 8 letters can receive a cost of 1 press.
• The most frequent letters should receive the cheapest positions, otherwise we would waste presses on characters that appear often.

The problem guarantees that every character is a lowercase English letter, so we only need to consider frequencies of the 26 letters.

Approaches

Brute Force

A brute-force solution would try all possible assignments of letters to keys and all possible orderings within each key.

For every mapping, we would calculate the total typing cost of the word and keep the minimum.

This approach is correct because it explicitly examines every valid keypad configuration and therefore cannot miss the optimal answer.

However, the number of possible assignments is enormous. Even assigning 26 letters among 8 keys already creates a combinatorial explosion, and ordering letters within keys makes it even worse. The search space is far beyond what can be explored in practice.

Therefore, brute force is completely infeasible.

Key Insight

The actual identities of the letters do not matter. Only their frequencies matter.

Suppose one letter appears 1000 times and another appears 10 times.

If the letter with frequency 1000 is assigned a cost of 2 presses while the letter with frequency 10 is assigned a cost of 1 press, swapping their positions would reduce the total cost by:

$$1000 \cdot 1 + 10 \cdot 2$$

instead of

$$1000 \cdot 2 + 10 \cdot 1$$

Thus, higher frequencies should always receive lower costs.

Since there are 8 keys:

• The first 8 most frequent letters can all receive cost 1.
• The next 8 most frequent letters receive cost 2.
• The next 8 most frequent letters receive cost 3.
• The remaining letters receive cost 4.

This becomes a simple greedy assignment problem.

We count character frequencies, sort them in descending order, then assign costs according to rank.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates keypad assignments
Optimal	O(n + 26 log 26)	O(26)	Frequency counting and greedy assignment

Algorithm Walkthrough

1. Count the frequency of every character in the word.

We need to know how many times each letter contributes to the final typing cost. A hash map or frequency counter is ideal for this task. 2. Extract all frequencies and sort them in descending order.

The most frequent letters should obtain the cheapest keypad positions. Sorting lets us process frequencies from largest to smallest. 3. Assign costs according to position in the sorted list.

Since there are 8 keys:

• Indices 0 through 7 receive cost 1
• Indices 8 through 15 receive cost 2
• Indices 16 through 23 receive cost 3
• Indices 24 through 25 receive cost 4

In general:

cost = index // 8 + 1

4. Multiply each frequency by its assigned cost.

Add the contribution of every letter to the running total. 5. Return the total cost.

Why it works

The greedy strategy is optimal because the cost positions are fixed. There are eight positions with cost 1, eight with cost 2, and so on.

If a lower-frequency letter is assigned a cheaper cost than a higher-frequency letter, swapping them can only decrease or preserve the total cost. Repeatedly applying this argument leads to an arrangement where frequencies are sorted in descending order and assigned to costs in ascending order.

This is exactly what the algorithm does, so it produces the minimum possible number of pushes.

Python Solution

from collections import Counter

class Solution:
    def minimumPushes(self, word: str) -> int:
        frequencies = sorted(Counter(word).values(), reverse=True)

        total_pushes = 0

        for index, frequency in enumerate(frequencies):
            cost = index // 8 + 1
            total_pushes += frequency * cost

        return total_pushes

The implementation begins by using Counter to compute character frequencies.

The frequency values are extracted and sorted in descending order so that the most common letters are processed first.

The loop assigns each frequency to its optimal cost slot. Because there are eight keys, every block of eight frequencies shares the same cost. The expression index // 8 + 1 directly computes the required number of presses for that rank.

Each frequency contributes frequency * cost to the answer, and the accumulated sum is returned.

Go Solution

package main

import "sort"

func minimumPushes(word string) int {
	freq := make(map[byte]int)

	for i := 0; i < len(word); i++ {
		freq[word[i]]++
	}

	frequencies := make([]int, 0, len(freq))
	for _, count := range freq {
		frequencies = append(frequencies, count)
	}

	sort.Slice(frequencies, func(i, j int) bool {
		return frequencies[i] > frequencies[j]
	})

	answer := 0

	for i, count := range frequencies {
		cost := i/8 + 1
		answer += count * cost
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

A map[byte]int stores character frequencies. The frequency values are copied into a slice and sorted in descending order using sort.Slice.

The cost calculation remains i/8 + 1, and the final answer is accumulated in an integer. Since the maximum answer is at most 100000 * 4 = 400000, standard Go int is more than sufficient.

Worked Examples

Example 1

word = "abcde"

Frequency table:

Letter	Frequency
a	1
b	1
c	1
d	1
e	1

Sorted frequencies:

[1, 1, 1, 1, 1]

Assignment:

Index	Frequency	Cost	Contribution
0	1	1	1
1	1	1	1
2	1	1	1
3	1	1	1
4	1	1	1

Total:

1 + 1 + 1 + 1 + 1 = 5

Answer:

5

Example 2

word = "xyzxyzxyzxyz"

Frequency table:

Letter	Frequency
x	4
y	4
z	4

Sorted frequencies:

[4, 4, 4]

Assignment:

Index	Frequency	Cost	Contribution
0	4	1	4
1	4	1	4
2	4	1	4

Total:

4 + 4 + 4 = 12

Answer:

12

Example 3

word = "aabbccddeeffgghhiiiiii"

Frequency table:

Letter	Frequency
i	6
a	2
b	2
c	2
d	2
e	2
f	2
g	2
h	2

Sorted frequencies:

[6, 2, 2, 2, 2, 2, 2, 2, 2]

Assignment:

Index	Frequency	Cost	Contribution
0	6	1	6
1	2	1	2
2	2	1	2
3	2	1	2
4	2	1	2
5	2	1	2
6	2	1	2
7	2	1	2
8	2	2	4

Total:

6 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 4 = 24

Answer:

24

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + 26 log 26)	Count frequencies, then sort at most 26 values
Space	O(26)	Store frequency counts

The dominant work is counting characters in the input string, which requires O(n) time. Although sorting is performed, there can be at most 26 distinct lowercase letters, making the sorting cost effectively constant. The extra memory usage is also bounded by the size of the alphabet.

Test Cases

sol = Solution()

assert sol.minimumPushes("abcde") == 5          # Example 1
assert sol.minimumPushes("xyzxyzxyzxyz") == 12  # Example 2
assert sol.minimumPushes("aabbccddeeffgghhiiiiii") == 24  # Example 3

assert sol.minimumPushes("a") == 1             # Single character
assert sol.minimumPushes("aaaaaa") == 6        # One distinct letter repeated

assert sol.minimumPushes("abcdefgh") == 8      # Exactly 8 unique letters
assert sol.minimumPushes("abcdefghi") == 10    # Ninth letter requires cost 2

assert sol.minimumPushes("abcdefghijklmnopqrstuvwxyz") == 56  # All 26 letters once

assert sol.minimumPushes("zzzzzzzzzz") == 10   # One very frequent letter

assert sol.minimumPushes("aaaabbbbccccddddeeeeffff") == 24  # Six letters, all cost 1

assert sol.minimumPushes(
    "abcdefghijklmnopqrstuvwxyz" * 3000
) == 168000  # Large input stress test

Test Summary

Test	Why
"abcde"	Verifies example 1
"xyzxyzxyzxyz"	Verifies example 2
"aabbccddeeffgghhiiiiii"	Verifies example 3
"a"	Smallest valid input
"aaaaaa"	Single distinct letter
"abcdefgh"	Exactly fills first cost tier
"abcdefghi"	First letter entering second tier
"abcdefghijklmnopqrstuvwxyz"	Uses all 26 letters
"zzzzzzzzzz"	One dominant frequency
"aaaabbbbccccddddeeeeffff"	Multiple high-frequency letters in first tier
Large repeated alphabet	Stress test near maximum size

Edge Cases

Only One Distinct Letter

A word such as "aaaaaa" contains a single unique character. Since there is no competition for cheap positions, that letter receives a cost of 1. The answer is simply the length of the word. Implementations that incorrectly assume every key must contain letters could produce larger costs, but this solution naturally assigns the single frequency to the cheapest slot.

More Than Eight Distinct Letters

A word like "abcdefghi" contains nine distinct characters. Only eight letters can occupy cost-1 positions because there are only eight keys. The ninth frequency must move into the cost-2 tier. The formula index // 8 + 1 handles this transition automatically.

All Twenty-Six Letters Present

When all lowercase letters appear, frequencies span four cost tiers. The first eight letters receive cost 1, the next eight receive cost 2, the next eight receive cost 3, and the final two receive cost 4. This is the largest possible number of distinct letters and validates that the algorithm correctly handles multiple tiers.

Extremely Long Input

The word length may reach 100000. A solution that tries to construct keypad layouts explicitly or explore assignments would be far too slow. This implementation only counts frequencies and sorts at most 26 values, so it easily handles the maximum input size.