Minimum Number of Keypresses - Practice Coding Problems

Minimum Number of Keypresses - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcde"

› Output: 5

💡 Note: Each letter appears once. Assign each to position 1 of different buttons: a(1), b(1), c(1), d(1), e(1) = 1+1+1+1+1 = 5 keypresses.

Example 2 — Repeated Letters

$ Input: s = "aabbcccdddd"

› Output: 11

💡 Note: Frequencies: d(4), c(3), a(2), b(2). Assign most frequent to position 1: d(1)×4 + c(1)×3 + a(1)×2 + b(1)×2 = 4+3+2+2 = 11.

Example 3 — Many Unique Letters

$ Input: s = "abcdefghijk"

› Output: 13

💡 Note: 11 unique letters, each appears once. First 9 letters get position 1 (9 keypresses), remaining 2 letters get position 2 (2×2=4 keypresses). Total: 9+4=13.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with letter frequencies to optimize

Process

Assign frequent letters to require fewer keypresses

Output

Minimum total keypresses needed

Key Takeaway

🎯 Key Insight: Assign most frequent letters to positions requiring fewest keypresses

Asked in

G Google 25 f Meta 20 a Amazon 15

The key insight is that we want to minimize total keypresses by assigning the most frequent letters to positions requiring fewer presses. The optimal approach uses frequency counting + greedy assignment: count letter frequencies, sort by frequency descending, then assign the most frequent letters to button position 1, next most frequent to position 2, etc. Time: O(n + k log k), Space: O(k) where k ≤ 26.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Random Assignment	O(26!)	O(26)	Try all possible letter assignments to buttons
Frequency Count + Greedy Assignment	O(n + k log k)	O(k)	Count letter frequencies and assign most frequent to position 1

Brute Force - Random Assignment — Algorithm Steps

Generate all valid letter-to-button assignments
For each assignment, calculate total keypresses for string s
Return minimum keypresses found

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how often each letter appears

Try Random Assignments

Randomly assign letters to button positions

Calculate & Compare

Sum keypresses and keep minimum

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

int solution(char* s) {
    int freq[26] = {0};
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    int minPresses = INT_MAX;
    srand(time(NULL));
    
    // Simplified brute force
    for (int trial = 0; trial < 1000; trial++) {
        int assignment[26];
        int letters[26];
        int letterCount = 0;
        
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                letters[letterCount++] = i;
            }
        }
        
        // Shuffle letters
        for (int i = letterCount - 1; i > 0; i--) {
            int j = rand() % (i + 1);
            int temp = letters[i];
            letters[i] = letters[j];
            letters[j] = temp;
        }
        
        int btn = 0, pos = 1;
        for (int i = 0; i < letterCount; i++) {
            assignment[letters[i]] = pos;
            pos++;
            if (pos > 3) {
                pos = 1;
                btn++;
            }
            if (btn >= 9) btn = 0;
        }
        
        int presses = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                presses += freq[i] * assignment[i];
            }
        }
        
        if (presses < minPresses) {
            minPresses = presses;
        }
    }
    
    return minPresses;
}

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(26!)

Factorial combinations of assigning 26 letters to button positions

✓ Linear Growth

Space Complexity

O(26)

Storage for current assignment mapping

✓ Linear Space

23.8K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Random Assignment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler