Leetcode 1516 Solution

This article provides solution to leetcode question 1516 (the-k-th-lexicographical-string-of-all-happy-strings-of-length-n)
Categories:
Tags:
Access this page by simply typing in "lcs 1516" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n

Solution

class Solution {
    std::string m_ans;

public:
    int search(vector<char>& curr, int i, int n, int k)
    {
        if (i == n || k < 0)
        {
            if (k == 0)
            {
                for (auto ch : curr)
                    m_ans += ch;
            }
            return 1;
        }

        int count = 0;
        char chars[3] = {'a', 'b', 'c'};
        for (int j = 0; j < 3; j++)
        {
            char ch = chars[j];
            if (curr.size() == 0 || ch != curr[curr.size() - 1])
            {
                curr.push_back(ch);
                count += search(curr, i + 1, n, k - count);
                curr.pop_back();
            }
        }

        return count;
    }

    string getHappyString(int n, int k) {
        vector<char> curr;
        search(curr, 0, n, k - 1);

        return m_ans;
    }
};