Learning Journal

2/10/2024

Minimum Number of Keypresses - 2nd attempt

function minimumKeypresses(s: string): number {
    if(s.length < 9) return s.length;

    const arr = Array(26).fill(0);

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

    arr.sort((a,b) => b - a);

    let numPresses = 0, i = 0;

    while(arr[i] > 0) {
        numPresses += arr[i]*(Math.floor(i/9) + 1);
        i++;
    }

    return numPresses;
};
function minimumKeypresses(s: string): number {
    if(s.length < 9) return s.length;

    const arr = Array(26).fill(0);

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

    arr.sort((a,b) => b - a);

    let numPresses = 0, i = 0;

    while(arr[i] > 0) {
        numPresses += arr[i]*(Math.floor(i/9) + 1);
        i++;
    }

    return numPresses;
};

THE PROBLEM

I added one improvement this time, and that is the conditional check at the beginning. If the string is shorter than 9, which means we can spread all of its characters to the 9 keys and each of them needs only 1 keypress. There is no need to check further.

Then, basically, the reasoning behind the algorithm is as followed:

If the string is longer than 9, the number of keypresses in total will equal to numPress * frequency in which numPress is the number of keypresses required and frequency is the number of its occurrence on the string. We cannot change frequency, so, our approach is to make the greater frequency the smaller the numPress. To know which character has the greater frequency, we can add all of the frequencies into an array then sort it in a descending order. And then, we distribute them evenly to the nine keys.

Revised by ChatGPT

I've implemented an improvement in this iteration by introducing a conditional check at the beginning of the function. If the string's length is less than 9, it means that we can assign each character to one of the 9 keys, with each character requiring only a single keypress. Thus, there's no need for further computation.

The logic behind the algorithm is as follows:

For strings longer than nine characters, the total number of keypresses required equals the product of the number of keypresses needed (numPress) and the frequency of each character's occurrence in the string (frequency). While we cannot alter the frequency, our strategy focusses on minimizing the numPress for characters with higher frequencies. To identify which characters appear more frequently, we tally the occurrences of each character in an array and then sort this array in descending order. Subsequently, we distribute these frequencies across the nine keys in a manner that assigns fewer keypresses to characters with higher frequencies.