Skip to content

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

  • Time: $O(3^n)$
  • Space: $O(3^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  string getHappyString(int n, int k) {
    const unordered_map<char, string> nextLetters{
        {'a', "bc"}, {'b', "ac"}, {'c', "ab"}};
    queue<string> q{{{"a", "b", "c"}}};

    while (q.front().length() != n) {
      const string u = q.front();
      q.pop();
      for (const char nextLetter : nextLetters.at(u.back()))
        q.push(u + nextLetter);
    }

    if (q.size() < k)
      return "";

    for (int i = 0; i < k - 1; ++i)
      q.pop();
    return q.front();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public String getHappyString(int n, int k) {
    Map<Character, String> nextLetters = Map.of('a', "bc", 'b', "ac", 'c', "ab");
    Queue<String> q = new ArrayDeque<>(Arrays.asList("a", "b", "c"));

    while (q.peek().length() != n) {
      final String u = q.poll();
      for (final char nextLetter : nextLetters.get(u.charAt(u.length() - 1)).toCharArray())
        q.offer(u + nextLetter);
    }

    if (q.size() < k)
      return "";

    for (int i = 0; i < k - 1; ++i)
      q.poll();
    return q.poll();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def getHappyString(self, n: int, k: int) -> str:
    nextLetters = {'a': 'bc', 'b': 'ac', 'c': 'ab'}
    q = collections.deque(['a', 'b', 'c'])

    while len(q[0]) != n:
      u = q.popleft()
      for nextLetter in nextLetters[u[-1]]:
        q.append(u + nextLetter)

    return '' if len(q) < k else q[k - 1]