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.

Description Hints 2 Solution Video 13:07

2268. Minimum Number of Keypresses

Medium71.2% acceptance1 companyPremium elsewhere, free here

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 <= 10⁵
s consists of lowercase English letters.

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Map the most frequent letters so that you can type them with only 1 keypress.

Hint 2

Use an array to keep track of the frequency of every character, then sort it in non-increasing order.

13:07

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"apple"

Input

"abcdefghijkl"

Your code is saved on this device.Solution