{x}
blog image

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

Solution Explanation

This problem asks to find the k-th lexicographical string of all happy strings of length n. A happy string is defined as a string consisting only of 'a', 'b', and 'c', where no two consecutive characters are the same.

The solution uses a depth-first search (DFS) or backtracking approach to generate all possible happy strings of length n and stores them in a list. It then returns the k-th string from the sorted list. If k exceeds the number of happy strings, it returns an empty string.

Algorithm:

  1. Base Case: If the length of the currently constructed string t equals n, it's a complete happy string, so add it to the ans list.

  2. Recursive Step: Iterate through 'a', 'b', and 'c'. For each character c:

    • Check if t is empty or the last character of t is different from c. This ensures we don't create consecutive identical characters.
    • If the condition is met, append c to t and recursively call dfs to explore further.
    • After the recursive call, remove the last character (c) from t to backtrack. This allows the exploration of different branches.

  3. Return Value: After generating all happy strings, the function checks if k is within the valid range (k <= len(ans)). If it is, it returns the k-1th element of ans (because lists are 0-indexed). Otherwise, it returns an empty string.

Time Complexity Analysis:

In the worst-case scenario, the algorithm needs to generate all possible happy strings. The number of happy strings of length n is approximately 3 * 2(n-1) (3 choices for the first character, and then 2 choices for each subsequent character to avoid repetition).

Therefore, the time complexity is O(3 * 2(n-1)), which is exponential.

Space Complexity Analysis:

The space complexity is determined by the size of the ans list and the recursion stack. In the worst case, the ans list can store all generated happy strings, which is O(3 * 2(n-1)). The recursion stack's depth is at most n. Thus, the overall space complexity is dominated by the list's size, making it O(3 * 2(n-1)).

Code Examples (Python, Java, C++)

The provided code snippets implement the above algorithm in Python, Java, and C++. They differ slightly in syntax but maintain the same underlying logic. Note the use of ans.get(k-1) in Java and ans[k-1] in Python and C++ to access the k-th string, accounting for the 0-based indexing of lists/vectors. The error handling for k being out of range is consistent across all examples.