Problem Description

You have a telephone keypad where keys 2-9 can be mapped to lowercase English letters. Similar to old phone keyboards, pressing a key multiple times cycles through its assigned letters. For example, if key 2 is mapped to ["a", "b", "c"], you need:

• 1 press to type "a"
• 2 presses to type "b"
• 3 presses to type "c"

Given a string word containing only lowercase English letters, you need to find the optimal way to remap the keys to minimize the total number of key presses needed to type the entire word.

Key constraints:

• You can remap keys 2-9 to any collection of letters
• Each key can have any number of letters assigned to it
• Each letter must be mapped to exactly one key
• You have 8 keys available (keys 2-9)

The solution uses a greedy approach: count the frequency of each letter in word, then assign the most frequent letters to positions that require fewer presses. The most frequent letters get assigned first (requiring 1 press), the next 8 most frequent letters require 2 presses, and so on.

For example, if a letter appears x times and is assigned to position i on a key (where position 1 requires 1 press, position 2 requires 2 presses, etc.), it contributes x * position to the total number of presses.

The code sorts letter frequencies in descending order and assigns them to keys in groups of 8, where:

• Letters 0-7 require 1 press each
• Letters 8-15 require 2 presses each
• Letters 16-23 require 3 presses each
• And so on...

The formula (i // 8 + 1) * x calculates the contribution of each letter, where i is the index in the sorted list and x is the frequency.

Intuition

To minimize the total number of key presses, we need to think about which letters should be easiest to type. Since we're typing the entire word, letters that appear more frequently will contribute more to the total count of key presses.

Consider a letter that appears 10 times versus one that appears only once. If the frequent letter requires 3 presses each time, it contributes 10 * 3 = 30 presses total. If the rare letter requires 3 presses, it only contributes 1 * 3 = 3 presses. This tells us that frequent letters should be assigned to positions requiring fewer presses.

Since we have 8 keys available (keys 2-9), we can assign up to 8 letters to require only 1 press each. The next 8 letters would require 2 presses each, and so on. This naturally leads to a greedy strategy:

1. Count how often each letter appears in the word
2. Sort letters by frequency (most frequent first)
3. Assign the most frequent letters to the "cheapest" positions

The key insight is that we want to minimize the expression: ∑(frequency[i] * presses_needed[i]) for all letters. Since we can't change the frequencies (they're determined by the input word), we minimize this sum by pairing high frequencies with low press counts.

This is similar to the problem of minimizing the dot product of two arrays - you pair the largest values from one array with the smallest values from the other. Here, we pair the largest frequencies with the smallest number of required presses (1, 1, 1, ..., 2, 2, 2, ..., 3, 3, 3, ...).

The formula (i // 8 + 1) elegantly captures this pattern: for indices 0-7, it gives 1 press; for indices 8-15, it gives 2 presses; and so on.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy algorithm combined with sorting to achieve the optimal key mapping:

Step 1: Count Letter Frequencies

cnt = Counter(word)

We use Python's Counter from the collections module to create a frequency map. This gives us a dictionary where keys are letters and values are their occurrence counts in the word.

Step 2: Sort Frequencies in Descending Order

sorted(cnt.values(), reverse=True)

We extract just the frequency values (we don't need to track which letter has which frequency) and sort them from highest to lowest. This ensures we process the most frequent letters first.

Step 3: Calculate Minimum Pushes

for i, x in enumerate(sorted(cnt.values(), reverse=True)):
    ans += (i // 8 + 1) * x

We iterate through the sorted frequencies with their indices:

• Index i represents the position in our sorted list (0-indexed)
• Value x is the frequency of that letter

The formula (i // 8 + 1) determines how many presses are needed:

• For indices 0-7: i // 8 = 0, so (0 + 1) = 1 press
• For indices 8-15: i // 8 = 1, so (1 + 1) = 2 presses
• For indices 16-23: i // 8 = 2, so (2 + 1) = 3 presses
• And so on...

Each letter contributes presses_needed * frequency to the total, which is (i // 8 + 1) * x.

Example Walkthrough: If word = "aabbccc", we get:

• cnt = {'a': 2, 'b': 2, 'c': 3}
• Sorted frequencies: [3, 2, 2]
• Calculations:
  • Index 0 (frequency 3): (0 // 8 + 1) * 3 = 1 * 3 = 3
  • Index 1 (frequency 2): (1 // 8 + 1) * 2 = 1 * 2 = 2
  • Index 2 (frequency 2): (2 // 8 + 1) * 2 = 1 * 2 = 2
• Total: 3 + 2 + 2 = 7

The algorithm achieves O(n) time for counting, O(26 log 26) for sorting (at most 26 distinct letters), resulting in O(n) overall time complexity with O(1) space complexity (since we store at most 26 letter counts).

Example Walkthrough

Let's walk through the solution with the word "hello".

Step 1: Count Letter Frequencies

• h: 1 occurrence
• e: 1 occurrence
• l: 2 occurrences
• o: 1 occurrence

So cnt = {'h': 1, 'e': 1, 'l': 2, 'o': 1}

Step 2: Sort Frequencies in Descending Order Extract and sort the frequency values: [2, 1, 1, 1]

Step 3: Assign Letters to Key Positions and Calculate Presses

Since we have 8 keys available, we can assign up to 8 letters to require only 1 press each. With only 4 distinct letters, they all get assigned to the first "tier" of positions.

Total minimum presses: 2 + 1 + 1 + 1 = 5

This means:

• The letter 'l' (appearing 2 times) gets the prime position on one key
• Letters 'h', 'e', and 'o' (each appearing once) also get assigned as the first letter on their respective keys
• To type "hello", we need 5 total key presses

Verifying with a different mapping scenario: If we had more than 8 distinct letters, some would require 2 presses. For instance, if we had 10 distinct letters with the 9th and 10th least frequent letters appearing 3 and 2 times respectively:

• The 9th letter (index 8): (8 // 8 + 1) × 3 = 2 × 3 = 6 presses
• The 10th letter (index 9): (9 // 8 + 1) × 2 = 2 × 2 = 4 presses

This demonstrates how the algorithm efficiently assigns more frequent letters to positions requiring fewer presses, minimizing the total number of key presses needed.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + |Σ| × log |Σ|), where n is the length of the string word and |Σ| is the size of the set of distinct characters that appear in the string.

• Creating the Counter takes O(n) time as it needs to iterate through all characters in the word
• The sorted() function on cnt.values() takes O(|Σ| × log |Σ|) time since we're sorting at most |Σ| frequency values
• The enumeration and calculation loop takes O(|Σ|) time as it processes each unique character once
• Overall: O(n) + O(|Σ| × log |Σ|) + O(|Σ|) = O(n + |Σ| × log |Σ|)

The space complexity is O(|Σ|):

• The Counter object stores at most |Σ| key-value pairs (one for each distinct character)
• The sorted list of values also contains at most |Σ| elements
• Other variables use constant space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Tracking Letter-to-Key Mappings

A common mistake is trying to maintain which specific letter maps to which key position, when the problem only requires calculating the minimum total presses. The greedy approach works because we only need frequencies, not the actual letter assignments.

Incorrect approach:

# Unnecessarily complex - trying to track exact mappings
key_mappings = {i: [] for i in range(2, 10)}
for i, (letter, freq) in enumerate(sorted(char_frequency.items(), key=lambda x: x[1], reverse=True)):
    key_num = 2 + (i % 8)
    key_mappings[key_num].append(letter)
    # ... calculate presses

Correct approach:

# Simple - just work with frequencies
sorted_frequencies = sorted(char_frequency.values(), reverse=True)
for index, frequency in enumerate(sorted_frequencies):
    total_pushes += ((index // 8) + 1) * frequency

2. Off-by-One Error in Press Calculation

Forgetting to add 1 when calculating the number of presses, since positions are 1-indexed (first position requires 1 press, not 0).

Incorrect:

pushes_per_char = index // 8  # Wrong! This gives 0 for first 8 letters

Correct:

pushes_per_char = (index // 8) + 1  # Correct: 1 press for first 8 letters

3. Using Wrong Division for Grouping

Using modulo (%) instead of integer division (//) when determining which "group of 8" a letter belongs to.

Incorrect:

pushes_per_char = (index % 8) + 1  # Wrong! This cycles through 1-8 repeatedly

Correct:

pushes_per_char = (index // 8) + 1  # Correct: groups letters into sets of 8

4. Forgetting to Handle Edge Cases

Not considering that the input might have fewer than 8 distinct letters or assuming all 26 letters appear.

Solution: The code naturally handles this by only iterating through actual frequencies present in the word, whether that's 1 letter or 26 letters.

5. Sorting in Wrong Order

Sorting frequencies in ascending order instead of descending, which would assign the most frequent letters to positions requiring more presses.

Incorrect:

sorted_frequencies = sorted(char_frequency.values())  # Ascending order - inefficient!

Correct:

sorted_frequencies = sorted(char_frequency.values(), reverse=True)  # Descending order