LeetCode 2268. Minimum Number of Keypresses

原题链接在这里：https://leetcode.com/problems/minimum-number-of-keypresses/description/

题目：

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.

题解：

Need to put the most frequent chars in the front of each button.

We put the 9 most frequent chars at the beginning of each button.

Then next 9 most frequent chars at the second of each button.

Time Complexity: O(n). n = s.length().

Space: O(1).

AC Java:

class Solution {
    public int minimumKeypresses(String s) {
        int[] count = new int[26];
        for(int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++;
        }

        Arrays.sort(count);
        int res = 0;
        int ind = 0;
        for(int i = 25; i >= 0; i--){
            res += count[i] * (ind / 9 + 1);
            ind++;
        }

        return res;
    }
}