Watch 10 video solutions for The k-th Lexicographical String of All Happy Strings of Length n, a medium level problem involving String, Backtracking. This walkthrough by codestorywithMIK has 13,473 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A happy string is a string that:
['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 <= 101 <= k <= 100Problem Overview: Given n and k, generate the k-th lexicographical happy string of length n. A happy string uses characters a, b, and c, and no two adjacent characters can be the same. If fewer than k such strings exist, return an empty string.
Approach 1: Backtracking Generation (Time: O(3 * 2^(n-1)), Space: O(n))
This approach uses backtracking to generate all valid happy strings in lexicographical order. Start with an empty string and recursively append characters from {a,b,c} that differ from the previous character. Each recursive call extends the string until length n. Because the choices are explored in sorted order, the generated strings are already lexicographically ordered. Maintain a counter and stop recursion once the k-th string is found. This method is straightforward and mirrors how you would enumerate combinations during an interview.
Approach 2: Iterative Enumeration with Counting (Time: O(n), Space: O(1) excluding output)
A more efficient method skips full enumeration by using the count of valid strings that start with a specific prefix. The total number of happy strings of length n is 3 * 2^(n-1). After fixing the first character, each additional position has exactly two valid choices (anything except the previous character). Use this property to determine how many strings exist for each prefix. Iterate through possible characters in lexicographical order and check whether the block of strings starting with that prefix contains the k-th string. If not, subtract the block size from k and move to the next candidate. This greedy selection builds the result character by character. The logic relies mainly on counting and simple string construction rather than recursion.
Recommended for interviews: Start with the backtracking solution to show understanding of constraint-based generation using backtracking. Then optimize with the counting-based iterative approach. Interviewers typically expect recognition that the search space follows a predictable pattern (3 * 2^(n-1)), allowing you to directly compute the k-th string in O(n) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Generation | O(3 * 2^(n-1)) | O(n) | When demonstrating recursion and constraint-based generation in interviews |
| Iterative Enumeration with Counting | O(n) | O(1) | When you need the k-th string directly without generating all possibilities |