Learning Journal

2/9/2024

Minimum Number of Keypresses

function minimumKeypresses(s: string): number {
    const arr = Array(26).fill(0);

    for(let i = 0; i < s.length; i++) {
        const index = s.charCodeAt(i) - 'a'.charCodeAt(0);
        arr[index]++;
    }

    arr.sort((a,b) => b - a);
    let i = 0, numPresses = 0;
    while(arr[i] > 0) {
        const curNumPresses = arr[i]*(Math.floor(i/9) + 1);
        numPresses += curNumPresses;
        i++;
    }

    return numPresses;    
};
function minimumKeypresses(s: string): number {
    const arr = Array(26).fill(0);

    for(let i = 0; i < s.length; i++) {
        const index = s.charCodeAt(i) - 'a'.charCodeAt(0);
        arr[index]++;
    }

    arr.sort((a,b) => b - a);
    let i = 0, numPresses = 0;
    while(arr[i] > 0) {
        const curNumPresses = arr[i]*(Math.floor(i/9) + 1);
        numPresses += curNumPresses;
        i++;
    }

    return numPresses;    
};

THE PROBLEM

This is my first attempt at solving this problem. The interesting thing about this problem (that I didn't know before figuring it out) is that it doesn't ask us to give back the number of keypresses given a pre-determined keyboard configuration. It also doesn't ask us to give back the number of keypresses in a random keyboard configuration. It gives us a string and askes us to find the optimal configuration for the keyboard.

So, the optimal configuration of the keyboard for a given string is all of the characters that have the greatest occurrences require the least amount of keypresses. The solution is we need to sort the characters in the string in the order of amount of occurrences that they have in the string in an descending order, so the greatest is placed first. Then, we place them one by one to the keyboard such that, all of them need 1 keypresses. When we fill up the 9 keys, we go back to place to the second place of the key, and so on.

Revised by ChatGPT

This was my first attempt at solving this problem. What I found interesting, and hadn't realized until I worked through it, is that the problem doesn't require us to calculate the number of keypresses for a predetermined keyboard configuration. Nor does it ask for the number of keypresses in a random keyboard layout. Instead, it presents us with a string and asks us to find the optimal keyboard configuration for that string.

The key to solving this problem lies in understanding that the optimal configuration for the keyboard is one where characters that occur most frequently require the fewest keypresses. To achieve this, we first sort the characters in the string by their frequency of occurrence in descending order, ensuring the most frequent characters are prioritized. We then assign these characters to the keyboard in such a way that initially, each character requires only one keypress. Once the first 9 keys are filled, we move on to assign characters to the second keypress level, and so on.

This approach ensures that the characters with the highest frequency are the easiest to type, thereby minimizing the total number of keypresses needed.