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 _theminimum 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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2200-2299/2268.Minimum%20Number%20of%20Keypresses/images/image-20220505184346-1.png)
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:

1
2
3
4
5
6
7
8
9


![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2200-2299/2268.Minimum%20Number%20of%20Keypresses/images/image-20220505203823-1.png)
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^5
s consists of lowercase English letters.

Solution

Method 1 – Greedy Frequency Assignment

Intuition

Assign the most frequent letters to the first position of each button, next most frequent to the second, and so on. This minimizes total keypresses.

Approach

Count frequency of each letter in s.
Sort frequencies descending.
For the top 9, each press costs 1; next 9 cost 2; last 8 cost 3.
Sum up total keypresses.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minimumKeypresses(string s) {
        vector<int> freq(26, 0);
        for (char c : s) freq[c-'a']++;
        sort(freq.rbegin(), freq.rend());
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            ans += freq[i] * (i/9 + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func minimumKeypresses(s string) int {
    freq := make([]int, 26)
    for _, c := range s { freq[c-'a']++ }
    sort.Slice(freq, func(i, j int) bool { return freq[i] > freq[j] })
    ans := 0
    for i := 0; i < 26; i++ {
        ans += freq[i] * (i/9 + 1)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


import java.util.*;
class Solution {
    public int minimumKeypresses(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c-'a']++;
        Arrays.sort(freq);
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            ans += freq[25-i] * (i/9 + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    fun minimumKeypresses(s: String): Int {
        val freq = IntArray(26)
        for (c in s) freq[c-'a']++
        freq.sortDescending()
        var ans = 0
        for (i in 0 until 26) {
            ans += freq[i] * (i/9 + 1)
        }
        return ans
    }
}

1
2
3
4
5
6


class Solution:
    def minimumKeypresses(self, s: str) -> int:
        from collections import Counter
        freq = sorted(Counter(s).values(), reverse=True)
        freq += [0] * (26 - len(freq))
        return sum(freq[i] * (i//9 + 1) for i in range(26))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


impl Solution {
    pub fn minimum_keypresses(s: String) -> i32 {
        let mut freq = vec![0; 26];
        for c in s.chars() { freq[c as usize - 'a' as usize] += 1; }
        freq.sort_by(|a, b| b.cmp(a));
        let mut ans = 0;
        for i in 0..26 { ans += freq[i] * (i/9 + 1); }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
    minimumKeypresses(s: string): number {
        const freq = Array(26).fill(0);
        for (const c of s) freq[c.charCodeAt(0) - 97]++;
        freq.sort((a, b) => b - a);
        let ans = 0;
        for (let i = 0; i < 26; ++i) ans += freq[i] * (Math.floor(i/9) + 1);
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n + 26 log 26) — n = length of s.
🧺 Space complexity: O(1) — only 26 counters.

Problem#

Examples#

Solution#

Method 1 – Greedy Frequency Assignment#

Intuition#

Approach#

Code#

Complexity#