The k-th Lexicographical String of All Happy Strings of Length n

Feb 18, 2025

Another backtracking problem where you are given some letter options to choice from to arrange permutations to explore. This one is a bit different cause you are tasked with finding all permutations containing just ‘a’, ‘b’ or ‘c’ letters, with no duplicates. For example a happy permutation is “abc”, and a non happy one would be ‘aab’.

You are given N for the amount of letters that should be in your generated sequence, and K for finding the Kth seqence if you were to sort all the seqences you found in a list. I like how leetcode’s hints tonight casually tried to get you to use more memory then you would need to.

Instead of generating an array of all my possible seqences, I just greedily backtrack using the already lexigraphically sorted string “abc”. I then just use a score varible to keep track of which Kth seqence I am currently at. If I have reached the Kth seqence, I just return out of my backtrack function and then return the answer.

Lastly, I know for sure there has to be some really cool math combinatrics trick for this problem, but I just couldn’t think of it, EI the backtracking for it just being seqences of 10 letters or less worked pretty well, but im sure if it were harder constraints I would be forced to somehow optimally use math to spit out a seqence.

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getHappyString = function(n, k) {
    let arr = new Array(n).fill('');
    let score = 1;
    let backtrack = function(I=0){
        if(I==n){
            if(score == k){
                return true;
            }
            score++;
            return false;
        }

        for(let chr of "abc"){
            if(I > 0 && arr[I-1] === chr){
                continue;
            }

            arr[I] = chr;
            if( backtrack(I+1) ){
                return true;
            }
            arr[I] = '';
        }
        return false;
    }

    backtrack();
    return arr.join("");
};

//A,_,_,_,_

Tags:

Backtracking