Minimum Number of Keypresses - Solution & Explanation

Problem Overview: You are given a string s representing characters typed on a classic phone keypad. Keys can map to multiple letters, and the number of presses required depends on the position of the letter on that key. The goal is to assign letters to keypad positions so the total number of keypresses needed to type s is minimized.

Approach 1: Brute Force Assignment (Exponential Time, High Space)

A direct idea is to try different assignments of the 26 letters across the available keypad positions and compute the total typing cost for each configuration. Each assignment determines how many presses are required for every letter in s. Since the number of possible permutations is extremely large, this quickly becomes infeasible. Time complexity grows factorially (approximately O(26!)) with large memory usage for tracking assignments, so this approach is only useful for reasoning about the problem rather than implementing it.

Approach 2: Frequency Sorting + Greedy (O(n log n) time, O(1) space)

The key insight is that letters used more frequently should require fewer keypresses. Count how often each character appears in the string using a small frequency array or hash table. Sort these frequencies in descending order. The first 8 most frequent characters should cost 1 press each, the next 8 cost 2 presses, the next 8 cost 3 presses, and the remaining characters cost 4 presses. Iterate through the sorted frequency list and compute the cost using presses = index / 8 + 1. Multiply the frequency by the presses required and accumulate the result. Sorting only 26 values makes this effectively linear in practice.

Approach 3: Counting + Greedy (O(n) time, O(1) space)

The optimal approach removes the explicit sort by relying on counting. First iterate through the string and count occurrences of each character. Since there are only 26 lowercase letters, the frequency structure has constant size. Place these counts into a small array and sort or bucket them efficiently. Then greedily assign the highest frequencies to the cheapest keypress slots. Because the alphabet size is fixed, the complexity becomes O(n) for scanning the string plus constant work for processing the counts. This technique combines greedy decision making with counting to achieve optimal performance.

Recommended for interviews: Interviewers expect the greedy frequency strategy. Recognizing that the most frequent characters should receive the lowest keypress cost demonstrates strong problem intuition. Start by counting character frequencies, then assign costs based on frequency ranking. The brute-force idea helps explain the optimization step, but the counting + greedy solution shows the algorithmic maturity interviewers look for.