1
class Solution {
2

3
  public String getHappyString(int n, int k) {
4
    List<String> innerList = new ArrayList<>();
5
    getHappyStringUtil(n, k, new char[] {'a', 'b', 'c'}, new StringBuilder(), innerList);
6
    if (innerList.size() < k) return "";
7
    return innerList.get(k - 1);
8
  }
9

10
  public void getHappyStringUtil(
11
      int n, int k, char[] letter, StringBuilder tempString, List<String> innerList) {
12
    // Base case
13
    if (tempString.length() == n) {
14
      innerList.add(tempString.toString());
15
      return;
16
    }
17

18
    // Recursive call
19
    for (int i = 0; i < 3; i++) {
20
      if (tempString.length() > 0 && tempString.charAt(tempString.length() - 1) == letter[i])
21
        continue;
22
      tempString.append(letter[i]);
23
      getHappyStringUtil(n, k, letter, tempString, innerList);
24
      tempString.deleteCharAt(tempString.length() - 1);
25
    }
26
  }
27
}