Problem Description

You have a keypad with 9 buttons numbered from 1 to 9. You need to map all 26 lowercase English letters to these buttons with the following rules:

• Every lowercase letter from 'a' to 'z' must be mapped to exactly one button
• Each button can have at most 3 characters mapped to it
• Once you decide the mapping, it cannot be changed

To type a character using the keypad:

• Press the button once to type the first character mapped to that button
• Press the button twice to type the second character mapped to that button
• Press the button three times to type the third character mapped to that button

Given a string s, you need to find the minimum number of total key presses required to type the entire string. You have the freedom to choose which characters are mapped to which buttons (within the constraints) to minimize the total key presses.

For example, if button 2 has characters 'a', 'b', 'c' mapped to it:

• To type 'a': press button 2 once (1 keypress)
• To type 'b': press button 2 twice (2 keypresses)
• To type 'c': press button 2 three times (3 keypresses)

The strategy is to map the most frequently occurring characters in the string to positions that require fewer key presses. Since we have 9 buttons and each can hold up to 3 characters, we can map:

• The 9 most frequent characters to the first position of each button (1 keypress each)
• The next 9 most frequent characters to the second position of each button (2 keypresses each)
• The remaining 8 characters to the third position of buttons (3 keypresses each)

Intuition

The key insight is that we want to minimize the total number of key presses, and we have complete control over how we map characters to buttons. This is a classic greedy optimization problem.

Think about it this way: if a character appears 100 times in the string and another appears only once, which one should require fewer key presses? Obviously, the one that appears 100 times should be easier to type (require fewer presses).

Since each button position requires a different number of presses:

• Position 1: 1 press
• Position 2: 2 presses
• Position 3: 3 presses

We should assign the most frequent characters to positions requiring fewer presses. With 9 buttons available:

• The 9 most frequent characters should go in position 1 of each button (1 press each)
• The next 9 most frequent characters should go in position 2 of each button (2 presses each)
• The remaining 8 characters (26 - 18 = 8) should go in position 3 of some buttons (3 presses each)

This greedy approach works because there's no interdependency between character assignments - placing a frequent character in a good position doesn't prevent us from placing another frequent character in another good position. We simply need to count character frequencies, sort them in descending order, and assign them to positions in order of increasing cost.

The total cost is then calculated as: frequency × keypresses_required for each character, where keypresses_required increases by 1 after every 9 characters are assigned.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows the greedy strategy we identified:

1. Count character frequencies: Use a Counter to count how many times each character appears in the string s. This gives us a dictionary where keys are characters and values are their frequencies.

2. Sort frequencies in descending order: Extract just the frequency values from the counter and sort them in descending order using sorted(cnt.values(), reverse=True). We don't need to track which character has which frequency since we only care about the total key presses.

3. Calculate total key presses:

   • Initialize ans = 0 to track the total key presses and k = 1 to track the current number of presses required per character
   • Iterate through the sorted frequencies with an index starting from 1
   • For each frequency x, add k * x to the answer (frequency × keypresses_required)
   • Every 9 characters (when i % 9 == 0), increment k by 1 since we've filled all 9 buttons at the current level and need to move to the next position

The algorithm works as follows:

• Characters 1-9 (most frequent) get assigned to position 1 of buttons 1-9, requiring 1 * frequency presses each
• Characters 10-18 get assigned to position 2 of buttons 1-9, requiring 2 * frequency presses each
• Characters 19-26 get assigned to position 3 of buttons 1-8, requiring 3 * frequency presses each

Time complexity: O(n + m log m) where n is the length of string s and m is the number of unique characters (at most 26) Space complexity: O(m) for storing the character counts

Example Walkthrough

Let's walk through a concrete example with the string s = "aabbccdddeee".

Step 1: Count character frequencies

• 'a' appears 2 times
• 'b' appears 2 times
• 'c' appears 2 times
• 'd' appears 3 times
• 'e' appears 3 times

Step 2: Sort frequencies in descending order Sorted frequencies: [3, 3, 2, 2, 2]

Step 3: Assign positions and calculate key presses

We have 9 buttons available, each with 3 positions:

• Position 1 (1 press): Can hold 9 characters
• Position 2 (2 presses): Can hold 9 characters
• Position 3 (3 presses): Can hold 8 characters

Let's process each frequency with its position cost:

Total key presses = 3 + 3 + 2 + 2 + 2 = 12

The algorithm assigns:

• The two most frequent characters (appearing 3 times each) to position 1 of buttons 1 and 2
• The three next frequent characters (appearing 2 times each) to position 1 of buttons 3, 4, and 5

Since we only have 5 unique characters and 9 position-1 slots available, all characters get the optimal 1-press positions. If we had more than 9 unique characters, characters 10-18 would require 2 presses each, and characters 19-26 would require 3 presses each.

The greedy approach ensures we minimize the total by always assigning the most frequent characters to the positions requiring the fewest presses.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + |Σ| × log |Σ|)

The time complexity consists of two main parts:

• O(n) for counting the frequency of each character in the string using Counter(s), where n is the length of the string
• O(|Σ| × log |Σ|) for sorting the frequency values, where |Σ| represents the number of distinct characters in the string

Since the problem deals with lowercase letters, |Σ| ≤ 26. The sorting operation dominates when the string has many distinct characters, while the counting operation dominates for very long strings with few distinct characters.

Space Complexity: O(|Σ|)

The space complexity is determined by:

• O(|Σ|) for the Counter dictionary that stores the frequency of each distinct character
• O(|Σ|) for the sorted list of frequency values

Both structures are bounded by the number of distinct characters in the string, which is at most 26 for lowercase letters, giving us an overall space complexity of O(|Σ|).

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

Common Pitfalls

Pitfall 1: Misunderstanding the Keypad Constraint

Issue: A common mistake is assuming we have 10 buttons (0-9) like a standard phone keypad, when the problem explicitly states we have 9 buttons numbered 1-9. This leads to incorrect calculations where developers use modulo 10 instead of modulo 9.

Incorrect Implementation:

def minimumKeypresses(self, s: str) -> int:
    char_frequency = Counter(s)
    total_keypresses = 0
    presses_per_char = 1
  
    for index, frequency in enumerate(sorted(char_frequency.values(), reverse=True), 1):
        total_keypresses += presses_per_char * frequency
      
        # WRONG: Using 10 instead of 9
        if index % 10 == 0:  
            presses_per_char += 1
  
    return total_keypresses

Solution: Always use 9 as the modulo value since we have exactly 9 buttons available.

Pitfall 2: Incorrect Index Handling

Issue: Starting the enumeration from 0 instead of 1 causes the press count to increment at the wrong positions. This happens when developers forget to specify the start parameter in enumerate().

Incorrect Implementation:

def minimumKeypresses(self, s: str) -> int:
    char_frequency = Counter(s)
    total_keypresses = 0
    presses_per_char = 1
  
    # WRONG: Starting from index 0
    for index, frequency in enumerate(sorted(char_frequency.values(), reverse=True)):
        total_keypresses += presses_per_char * frequency
      
        # This will increment after 9th, 18th character instead of after 9th, 18th
        if (index + 1) % 9 == 0:  
            presses_per_char += 1
  
    return total_keypresses

Solution: Use enumerate(sorted_frequencies, 1) to start counting from 1, or adjust the modulo check accordingly if starting from 0.

Pitfall 3: Attempting to Track Character-to-Button Mapping

Issue: Some developers try to maintain the actual mapping of characters to buttons, which unnecessarily complicates the solution and doesn't affect the final answer.

Overcomplicated Implementation:

def minimumKeypresses(self, s: str) -> int:
    char_frequency = Counter(s)
    button_mapping = {i: [] for i in range(1, 10)}  # UNNECESSARY
  
    sorted_chars = sorted(char_frequency.items(), key=lambda x: x[1], reverse=True)
  
    button_num = 1
    position = 0
    total_keypresses = 0
  
    for char, freq in sorted_chars:
        button_mapping[button_num].append(char)  # UNNECESSARY
        total_keypresses += (position + 1) * freq
      
        button_num += 1
        if button_num > 9:
            button_num = 1
            position += 1
  
    return total_keypresses

Solution: Focus only on frequencies and their positions. The actual character-to-button assignment doesn't matter for calculating the minimum keypresses - only the frequencies and their optimal positioning matter.