Leetcode 1663. The minimum string with the given numerical | punch brush

Topic link

Greedy algorithm

Train of thought

I need to find the string with the smallest lexicographical order. According to greedy thinking, I want the smallest. First, fill all characters of length N with A, and then replace A from back to front.

code

function getSmallestString(n: number, k: number) :string {
    let arr = new Array(n).fill('a'); // Initializes an array of strings, all filled with 'a'

    // Fill from back to front, replace 'a'
    while (n > 0) {
        // if you can fill in 'z', fill in 'z'.
        if (k - 26 > n - 1) {
            arr[n - 1] = 'z';
            k -= 26;
        } else if (k > n) {
            // Fill the largest fill
            const dicIndex = k - n;
            arr[n - 1] = String.fromCharCode('a'.charCodeAt(0) + dicIndex);
            k -= dicIndex + 1;
        } else {
            break;
        }
        // Go ahead and replace 'a'
        n--;
    }

    return arr.join(' ');
};
Copy the code