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

In this guide, you will get 1415. The k-th Lexicographical String of All Happy Strings of Length n LeetCode Solution with the best time and space complexity. The solution to The k-th Lexicographical String of All Happy Strings of Length n problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. The k-th Lexicographical String of All Happy Strings of Length n solution in C++
4. The k-th Lexicographical String of All Happy Strings of Length n solution in Java
5. The k-th Lexicographical String of All Happy Strings of Length n solution in Python
6. Additional Resources

Problem Statement of The k-th Lexicographical String of All Happy Strings of Length n

A happy string is a string that:

consists only of letters of the set [‘a’, ‘b’, ‘c’].
s[i] != s[i + 1] for all values of i from 1 to s.length – 1 (string is 1-indexed).

For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.
Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.
Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

Example 1:

Input: n = 1, k = 3
Output: “c”
Explanation: The list [“a”, “b”, “c”] contains all happy strings of length 1. The third string is “c”.

Example 2:

Input: n = 1, k = 4
Output: “”
Explanation: There are only 3 happy strings of length 1.

Example 3:

Input: n = 3, k = 9
Output: “cab”
Explanation: There are 12 different happy string of length 3 [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”]. You will find the 9th string = “cab”

Constraints:

1 <= n <= 10
1 <= k <= 100

Complexity Analysis

• Time Complexity: O(3^n)
• Space Complexity: O(3^n)

1415. The k-th Lexicographical String of All Happy Strings of Length n LeetCode Solution in C++

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();
  }
};
/* code provided by PROGIEZ */

1415. The k-th Lexicographical String of All Happy Strings of Length n LeetCode Solution in Java

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<>(List.of("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();
  }
}
// code provided by PROGIEZ

1415. The k-th Lexicographical String of All Happy Strings of Length n LeetCode Solution in Python

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]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.