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

class Solution {
public:
    stack<char> st;
    vector<string> sp;
    void rec(int curr,int n){
        if(curr==n){
            string temp="";
            while(!st.empty()){
                temp+=st.top();
                st.pop();
            }
            reverse(temp.begin(),temp.end());
            for(auto it: temp)
                st.push(it);
            sp.push_back(temp);
            return ;
        }
        int miss= st.top()-'a';
        for(int i=0;i<3;++i){
            if(i==miss) continue;
            st.push('a'+i);
            rec(curr+1,n);
            st.pop();
        }
    }
    string getHappyString(int n, int k) {
        sp.clear();
        if(n==0) return "";
        while(!st.empty())
            st.pop();
        st.push('a');
        rec(1,n);
        while(!st.empty())
            st.pop();
        st.push('b');
        rec(1,n);
        while(!st.empty())
            st.pop();
        st.push('c');
        rec(1,n);
        if(sp.size()<k) return "";
        return sp[k-1];
    }
};