Skip to main content
Talentd

The k-th Lexicographical String of All Happy Strings of Length n - Solution & Explanation

MediumStringBacktracking38 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Backtracking Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Enumeration

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: DFS

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:

  1. If the length of the current string is equal to n, add the current string to the answer array ans and return;
  2. If the length of the answer array is greater than or equal to k, return directly;
  3. Otherwise, we iterate over the character set {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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Approach 4: Mathematics

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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

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.

Iterative Enumeration

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.

DFS—
Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking GenerationO(3 * 2^(n-1))O(n)When demonstrating recursion and constraint-based generation in interviews
Iterative Enumeration with CountingO(n)O(1)When you need the k-th string directly without generating all possibilities

Video Solution

The k-th Lexicographical String of All Happy Strings of Length n | Leetcode 1415 | codestorywithMIK • codestorywithMIK • 13,913 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is The k-th Lexicographical String of All Happy Strings of Length n easy or hard?
The problem is generally rated Medium because the brute-force backtracking approach is straightforward but recognizing the counting pattern requires deeper insight. Understanding that the number of valid strings follows 3 * 2^(n-1) enables a more optimal O(n) solution.
The k-th Lexicographical String of All Happy Strings of Length n Python/Java solution
Python and Java implementations typically follow either recursive backtracking or iterative counting. Backtracking recursively appends characters while skipping duplicates with the previous character. The optimized version computes how many strings exist for each prefix and selects characters greedily to build the result in O(n).
How to solve The k-th Lexicographical String of All Happy Strings of Length n in O(n)?
Use a counting-based greedy method. At each position, check how many valid strings can be formed with a candidate character while respecting the 'no adjacent duplicates' rule. If the block size is smaller than k, subtract it and move to the next candidate; otherwise choose that character and continue. This constructs the result in linear time.
What is the best approach for The k-th Lexicographical String of All Happy Strings of Length n?
The optimal approach uses counting with iterative enumeration. Instead of generating every happy string, calculate how many strings exist for each prefix using the formula 3 * 2^(n-1). This allows you to determine which character belongs at each position and build the k-th lexicographical string directly in O(n) time.
Is The k-th Lexicographical String of All Happy Strings of Length n asked at Google/Amazon/Meta?
Variants of this problem appear in interviews that test backtracking, combinatorial enumeration, and lexicographic ordering. Companies like Google, Amazon, and Meta frequently use similar string generation or k-th permutation style questions to evaluate problem decomposition and counting optimizations.
What data structure is used in The k-th Lexicographical String of All Happy Strings of Length n?
The backtracking solution mainly uses recursion and a dynamic string builder to construct candidates. The optimized solution relies on simple variables and counting logic rather than heavy data structures, making it closer to a greedy combinatorial approach.
What is the time complexity of The k-th Lexicographical String of All Happy Strings of Length n?
The backtracking solution takes O(3 * 2^(n-1)) time because it may generate every valid happy string of length n. The optimized counting approach runs in O(n) time since it determines each character position using precomputed counts rather than exploring all possibilities.

Ready to solve this problem?

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
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring