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.
This approach uses backtracking to generate all happy strings of the specified length n. The basic idea is to build strings character by character, ensuring at each step that the string remains 'happy' by not placing the same character consecutively. Once we have built a string of length n, we check if it is the k-th string that satisfies the conditions. This approach helps efficiently generate and count possible strings.
In the C solution, we use a recursive function generateHappyStrings to create strings of length n only using characters 'a', 'b', and 'c'. During recursion, we ensure a newly added character is different from the previous one. We use reference counting to track the number of valid happy strings constructed and compare it with k to check if we've reached the k-th string. If less than k strings are possible, an empty string is returned.
Time complexity is O(3^n) since each of the n positions can be filled in at most 3 ways. Space complexity is O(n) due to the recursion stack and storing strings up to length n.
An iterative approach can be used to generate strings by systematically constructing valid combinations of happy strings. Starting from 'a', 'b', 'c', you extend each string by appending characters that are different from the last one. Use a queue or list data structure for an efficient breadth-first construction of each happy string, and stop when the k-th string is constructed.
The C implementation uses a queue to iteratively build and explore possible happy strings. Starting with single characters, it appends each viable option until a string of desired length is achieved. It tracks the construction using breadth-first logic to monitor each level's string completion. A counter helps ascertain when the k-th valid configuration is reached, extracting and returning it thereafter. If fewer than k possible strings exist, an empty string is produced.
Time complexity is O(3^n) due to queue-based string generation. Space complexity is also O(3^n) for queue storage of possible strings during construction.
We use a string s to record the current string, initially an empty string. Then, we design a function dfs to generate all happy strings of length n.
The implementation of the function dfs is as follows:
n, add the current string to the answer array ans and return;k, return directly;{a, b, c}. For each character c, if the current string is empty or the last character of the current string is not equal to c, add the character c to the current string, then recursively call dfs. After the recursion ends, remove the last character of the current string.Finally, we check if the length of the answer array is less than k. If it is, return an empty string; otherwise, return the k-th element of the answer array.
The time complexity is O(n times 2^n), and the space complexity is O(n). Here, n is the length of the string.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
We can directly calculate what the k-th happy string is, without generating all happy strings.
Starting from the first happy string of length n, we can determine what each character position should be.
For a happy string of length n, the first character has 3 choices, the second character has 2 choices (cannot be the same as the first), the third character also has 2 choices (cannot be the same as the second), and so on, until the n-th character also has 2 choices (cannot be the same as the (n-1)-th). Therefore, the total number of happy strings of length n is 3 times 2^{n-1}.
If k is greater than the total number of happy strings of length n, we return an empty string directly.
Otherwise, we start from the first character and determine each character's position one by one. For the i-th character, we enumerate the character set {a, b, c}. If the last character of the current string is not equal to c, we calculate the number of remaining happy strings. If k is less than or equal to that count, we append character c to the current string and move on to the next position; otherwise, we subtract that count from k and continue enumerating the next character.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time complexity is |
| Iterative Enumeration | Time complexity is |
| DFS | — |
| Mathematics | — |
| 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 |
The k-th Lexicographical String of All Happy Strings of Length n | Leetcode 1415 | codestorywithMIK • codestorywithMIK • 13,473 views views
Watch 9 more video solutions →Practice The k-th Lexicographical String of All Happy Strings of Length n with our built-in code editor and test cases.
Practice on FleetCode