1
class Solution {
2
 private:
3
  void happy(string s, vector<char> &v, int n, vector<string> &ans) {
4
    if (s.size() == n) {
5
      ans.push_back(s);
6
      return;
7
    }
8
    for (int i = 0; i < 3; i++) {
9
      if (s.back() != v[i]) {
10
        s.push_back(v[i]);
11
        happy(s, v, n, ans);
12
        s.pop_back();
13
      }
14
    }
15
  }
16

17
 public:
18
  string getHappyString(int n, int k) {
19
    vector<char> v = {'a', 'b', 'c'};
20
    vector<string> ans;
21
    string s = "";
22
    happy(s, v, n, ans);
23
    if (ans.size() < k) {
24
      return "";
25
    } else {
26
      return ans[k - 1];
27
    }
28
  }
29
};