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

Leetcode Problem:

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

Summary

• This problem is to find the kth happy string of a given length n, where happy string is a string that consists only of letters a, b, c and s[i]!= s[i + 1] for all values of i from 1 to n - 1.

Approach

• The approach used in this solution is a recursive function that generates all happy strings of a given length n
• The function uses a dynamic programming approach to keep track of the number of happy strings generated so far and returns the kth string when k is reached.

Complexity

• O(3^n) because in the worst case, for each position in the string, there are 3 possible choices for the character, and this choice is made n times.

Explanation

• The solution uses a recursive function getHappyString that takes four parameters: n (the length of the string), k (the position of the string we want to find), depth (the current position in the string), and res (the string generated so far)
• The function first checks if the length of the string is equal to the depth
• If it is, it increments the count of happy strings and checks if the count is equal to k
• If it is, it returns the string
• If not, it returns an empty string
• If the length of the string is not equal to the depth, the function loops through each character in the set {a, b, c} and recursively calls itself with the next depth and the current character appended to the result string
• If the recursive call returns a non-empty string, it returns that string
• Otherwise, it returns an empty string.

Solution Code:

class Solution {
public:
    char c[3] = {'a', 'b', 'c'};
    int cnt;
    string getHappyString(int n, int k, int depth = 0, string res = "") {
        if(n == depth){
            cnt++;
            if(cnt == k){
                return res;
            }
            return "";
        }
        for(int i = 0 ; i < 3; i++){
            if(depth != 0 && res[depth-1] == c[i]){
                continue;
            }
            string ans = getHappyString(n, k, depth + 1, res + c[i]);
            if(ans.size() != 0){
                return ans;
            }
        }
        return "";
    }
};