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

A happy string is a string that:

• consists only of letters of the set [‘a’, ‘b’, ‘c’].
• s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.

Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

class Solution {
    bool helper(string& s, int n, int& k) {
        if(s.length() == n) {
            return --k == 0;
        } else {
            for(int i = 0; i < 3; i++) {
                if(s.empty() or s.back() != ('a' + i)) {
                    s.push_back('a' + i);
                    if(helper(s,n,k))
                        return true;
                    s.pop_back();
                }
            }
            return false;
        }
    }
public:
    string getHappyString(int n, int k) {
        string res = "";
        helper(res,n,k);
        return res;
    }
};