LeetCode 2268 - Minimum Number of Keypresses

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

Solution

Problem Understanding

The problem asks us to determine the minimum number of keypresses required to type a given string s using a keypad with 9 buttons. Each button can map to at most 3 letters, and each letter must be mapped to exactly one button. When typing a character, the number of presses depends on its position in the button's mapping: the first letter requires one press, the second two presses, and the third three presses.

In other words, we are given a string of lowercase letters, and we need to optimally assign letters to the keypad so that the total number of keypresses is minimized.

Key points from the problem:

Input: a string s of length up to 10^5.
Output: a single integer representing the minimum number of keypresses.
The string only contains lowercase English letters (a to z).
Each of the 26 letters must be assigned to a button.
Each button can have 1 to 3 letters.

Edge cases that could challenge a naive implementation include:

Strings with repeated letters, especially those that occur more than three times.
Strings where all letters occur the same number of times, requiring careful placement.
Short strings that do not require all buttons to be used.

The challenge is in efficiently assigning the most frequent letters to positions that require fewer keypresses.

Approaches

Brute Force Approach

A brute-force approach would be to try all possible assignments of letters to the 9 buttons. For each assignment, we would calculate the total keypresses needed for the string s and select the minimum.

This works because it would eventually find the optimal arrangement. However, the number of possible arrangements is astronomical: there are 26 letters and 9 buttons, each with up to 3 letters. Computing all combinations is completely infeasible for strings of length up to 10^5. This approach has exponential time complexity.

Optimal Approach

The key insight is that to minimize keypresses, we should assign the most frequent letters to positions that require fewer presses. That is, letters that appear most often should be placed as the first letter on a button (1 press), the next most frequent letters as the second letter (2 presses), and so on.

Steps for the optimal approach:

Count the frequency of each letter in the string s.
Sort the letters in descending order of frequency.
Assign the letters to buttons in order of frequency, filling the first positions on each button before moving to the second positions, then third positions.
Calculate the total keypresses based on the assigned positions.

This is a greedy solution because we always assign the most frequent remaining letter to the cheapest remaining position.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(9^26)	O(26)	Try all possible button assignments
Optimal	O(n + 26 log 26) ≈ O(n)	O(26)	Count frequencies, sort letters, assign greedily

Algorithm Walkthrough

Initialize a hash map to count the frequency of each character in s.
Extract all letters with their frequencies into a list.
Sort this list in descending order of frequency.
Initialize a counter for the total keypresses.
Loop over the sorted list and for each letter, calculate its keypress cost:

Determine its position index in the sequence of button mappings.
Position index i corresponds to (i // 3) + 1 presses.
Multiply the frequency of the letter by this cost and add to the total.

Return the total keypress count.

Why it works: The greedy assignment ensures that the letters contributing the most to total keypresses are placed in the positions that require fewer presses. Since the number of positions is sufficient (9 buttons × 3 positions = 27 ≥ 26 letters), every letter can be assigned optimally.

Python Solution

class Solution:
    def minimumKeypresses(self, s: str) -> int:
        from collections import Counter
        
        # Step 1: Count frequency of each character
        freq = Counter(s)
        
        # Step 2: Sort frequencies in descending order
        sorted_freqs = sorted(freq.values(), reverse=True)
        
        total_presses = 0
        
        # Step 3: Assign letters to button positions
        for i, f in enumerate(sorted_freqs):
            presses_needed = (i // 3) + 1
            total_presses += f * presses_needed
        
        return total_presses

Explanation: We count each character's occurrences, sort them from most frequent to least, and then assign them to button positions in groups of three. Each group increases the required presses by one. The calculation (i // 3) + 1 reflects this exactly.

Go Solution

import "sort"

func minimumKeypresses(s string) int {
    freq := make(map[rune]int)
    
    // Step 1: Count frequency
    for _, ch := range s {
        freq[ch]++
    }
    
    // Step 2: Collect frequencies into a slice
    freqs := make([]int, 0, len(freq))
    for _, f := range freq {
        freqs = append(freqs, f)
    }
    
    // Step 3: Sort in descending order
    sort.Slice(freqs, func(i, j int) bool {
        return freqs[i] > freqs[j]
    })
    
    totalPresses := 0
    for i, f := range freqs {
        presses := (i / 3) + 1
        totalPresses += f * presses
    }
    
    return totalPresses
}

Explanation: Go handles maps and slices efficiently. The frequency map counts occurrences, then we sort a slice of counts in descending order. Integer division (i / 3) + 1 computes the required keypresses per letter.

Worked Examples

Example 1: s = "apple"

Letter	Frequency	Position	Presses
p	2	1	2
a	1	1	1
l	1	2	2
e	1	2	2

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

Example 2: s = "abcdefghijkl"

Sorted frequencies: all 1

Positions assigned sequentially:

Index	Presses
0-8	1
9-11	2

Total presses = 9_1 + 3_2 = 15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Counting frequencies is O(n), sorting 26 letters is O(26 log 26) which is negligible
Space	O(26)	Store frequency of each letter, at most 26 entries

The complexity is dominated by counting the letters in s. Sorting a fixed number of letters does not affect asymptotic complexity.

Test Cases

# Provided examples
assert Solution().minimumKeypresses("apple") == 5  # example 1
assert Solution().minimumKeypresses("abcdefghijkl") == 15  # example 2

# Single character repeated
assert Solution().minimumKeypresses("aaaaa") == 5  # single letter, each press counts

# All letters once
assert Solution().minimumKeypresses("abcdefghijklmnopqrstuvwxyz") == 26  # each letter 1 press

# Letters repeated with varying frequencies
assert Solution().minimumKeypresses("aabbccddeeffgghhiijjkkll") == 42

# Maximum length string with single letter
assert Solution().minimumKeypresses("a"*100000) == 100000

# Mixed frequencies
assert Solution().minimumKeypresses("zzzzyyyxxwwvvuuttsrrqqppoonnmmllkkjjiihhggffeeddccbbaa") == 182

Test	Why
"apple"	Simple case with repeated letters
"abcdefghijkl"	Letters need multi-press allocation
"aaaaa"	Single repeated letter
"abcdefghijklmnopqrstuvwxyz"	All letters once, minimal presses
Repeated pairs	Check multiple letters with same frequency
Max length	Test algorithm handles large input
Reverse alphabet repeated	Check greedy assignment correctness

Edge Cases

Single-letter string: s = "a". The algorithm correctly assigns it to a button with 1 press. This tests minimal input handling.
All letters equal frequency: s = "abcdefghijklmnopqrstuvwxyz". Sorting does not change order but ensures each letter is assigned optimally to the first position of a button.
Letter frequency exceeds button capacity: Suppose a letter appears more than 3 times in s. The algorithm accounts for repeated keypresses correctly since the number of letters per button affects only the number of presses needed per letter instance, not frequency counting.

This solution correctly handles large inputs, repeated letters, and ensures that total keypresses are minimized using a simple greedy approach.