Skip to main content
Talentd

Minimum Number of Keypresses - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringGreedySorting9 min readAsked at: Amazon
Practice this problem

Problem Statement

You have a keypad with 9 buttons, numbered from 1 to 9, each mapped to lowercase English letters. You can choose which characters each button is matched to as long as:

  • All 26 lowercase English letters are mapped to.
  • Each character is mapped to by exactly 1 button.
  • Each button maps to at most 3 characters.

To type the first character matched to a button, you press the button once. To type the second character, you press the button twice, and so on.

Given a string s, return the minimum number of keypresses needed to type s using your keypad.

Note that the characters mapped to by each button, and the order they are mapped in cannot be changed.

 

Example 1:

Input: s = "apple"
Output: 5
Explanation: One optimal way to setup your keypad is shown above.
Type 'a' by pressing button 1 once.
Type 'p' by pressing button 6 once.
Type 'p' by pressing button 6 once.
Type 'l' by pressing button 5 once.
Type 'e' by pressing button 3 once.
A total of 5 button presses are needed, so return 5.

Example 2:

Input: s = "abcdefghijkl"
Output: 15
Explanation: One optimal way to setup your keypad is shown above.
The letters 'a' to 'i' can each be typed by pressing a button once.
Type 'j' by pressing button 1 twice.
Type 'k' by pressing button 2 twice.
Type 'l' by pressing button 3 twice.
A total of 15 button presses are needed, so return 15.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

Approach Overview

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.

Solution

First, we count the occurrence of each character in the string s, and record it in an array or hash table cnt.

The problem requires minimizing the number of key presses, so the 9 most frequent characters should correspond to keys 1 to 9, the 10th to 18th most frequent characters should correspond to keys 1 to 9 again, and so on.

Therefore, we can sort the values in cnt in descending order, and then allocate them to the keys in the order from 1 to 9, adding 1 to the number of key presses after allocating every 9 characters.

The time complexity is O(n + |\Sigma| times log |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the string s, and \Sigma is the set of characters appearing in the string s. In this problem, \Sigma is the set of lowercase letters, so |\Sigma| = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Letter AssignmentO(26!)HighConceptual reasoning about the problem; not practical for implementation
Frequency Sorting + GreedyO(n log n)O(1)Simple implementation when sorting character frequencies
Counting + GreedyO(n)O(1)Optimal solution using fixed alphabet counting and greedy assignment

Video Solution

MINIMUM NUMBER OF KEYPRESSES | LEETCODE 2268 | PYTHON GREEDY SOLUTION • Cracking FAANG • 3,750 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Minimum Number of Keypresses easy or hard?
Minimum Number of Keypresses is classified as Medium difficulty on LeetCode. The implementation is straightforward once you recognize the greedy insight that higher-frequency characters should receive lower keypress costs.
Minimum Number of Keypresses Python/Java solution
The implementation counts character frequencies, sorts them in descending order, and calculates presses using index / 8 + 1. This logic translates directly to Python, Java, C++, Go, and TypeScript because it only requires arrays, sorting, and simple arithmetic.
How to solve Minimum Number of Keypresses in O(n)?
First count occurrences of each lowercase letter using a 26-length array. Then sort or rank these frequencies and assign the cheapest keypress positions to the most frequent characters. Because the alphabet size is constant, sorting and assignment take constant time, making the overall complexity O(n).
What is the best approach for Minimum Number of Keypresses?
The best approach is a greedy strategy based on character frequency. Count how often each letter appears in the string, sort frequencies in descending order, and assign the most frequent letters to the cheapest keypress slots. The first 8 letters cost 1 press, the next 8 cost 2 presses, and so on. This minimizes the total typing cost.
Is Minimum Number of Keypresses asked at Google/Amazon/Meta?
Greedy frequency assignment problems similar to this one appear in interviews at large companies such as Google, Amazon, and Meta. The question tests your ability to recognize optimization opportunities and map frequent elements to lower costs.
What data structure is used in Minimum Number of Keypresses?
The main data structure is a frequency array or hash table that counts how many times each character appears in the string. After counting, a small array or list is used to sort frequencies and apply the greedy assignment of keypress costs.
What is the time complexity of Minimum Number of Keypresses?
The optimal solution runs in O(n) time where n is the length of the input string. You scan the string once to compute character frequencies and then process a fixed array of 26 letters to assign keypress costs. Space complexity is O(1) because the alphabet size is constant.

Ready to solve this problem?

Practice Minimum Number of Keypresses with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters