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

A good algorithm speaks for itself.

Jokes, you just recurse through all the possible strings, and increment a count variable everytime you reach a valid happy string Eventually, once you reach the kth happy string, you can just break out of the recursion and return the string directly.

code

class Solution {
public:
    bool recursion (int &count, int n, int k, string& happy) {
        if (happy.size() == n) {
            if (++count == k) {
                return true;
            } else {
                return false;
            }
        }

        for (int i = 0; i < 3; ++i) {
            if (happy.size() > 0 && happy.back() == 'a'+i) continue;

            happy += 'a'+i;
            if (recursion(count, n, k, happy)) {
                return true;
            }
            happy.pop_back();
        }
        return false;
    }
    string getHappyString(int n, int k) {
        string happy = "";
        int count = 0;
        recursion(count, n, k, happy);
        return happy;
    }
};

complexity

• Time: O(k * n)
• Space: O(n^2)

time taken

• 6 minutes and 29.71 seconds (I might be a bit of a beast)