The k-th Lexicographical String of All Happy Strings of Length n solution and explanation
Google
9 more videos on this problem
The k-th Lexicographical String of All Happy Strings of Length n | Leetcode 1415 | codestorywithMIKcodestorywithMIK · 35:25 · 13K views
The k-th Lexicographical String of All Happy Strings of Length n - Leetcode 1415 - PythonNeetCodeIO · 18:57 · 10K views
The k th Lexicographical String of All Happy Strings of Length n | Leetcode 1415Techdose · 15:41 · 4K views
1415. The k-th Lexicographical String of All Happy Strings of Length n | Recrsion | Backtrack | MathAryan Mittal · 30:54 · 2K views
1415. The k-th Lexicographical String of All Happy Strings of Length n | leetcode daily challenge |ShashCode · 11:51 · 2K views
Daily Leetcode #2174: Mar 14, 2026 - 1415. The k-th Lexicographical String of All Happy Strings ofProgramming Live with Larry · 16:27 · 390 views
1415. The k-th Lexicographical String of All Happy Strings of Length n | Leetcode Daily - PythonLeetcode Daily · 9:45 · 355 views
LeetCode 1415 | K-th Lexicographical Happy String of Length n | Backtracking Explained 🔥AlgoDiary · 17:12 · 281 views
The k th Lexicographical String of All Happy Strings of Length n || Leetcode || 1415Perceiver · 7:48 · 205 views
LeetCode 1415 | The K-th Lexicographical Happy String 🔥| Backtracking Explained | Java SolutioncodeWithKhan · 23:57 · 130 views
The problem
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 ofifrom1tos.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 <= 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.
def getHappyString(n: int, k: int) -> str:
def backtrack(current: str):
if len(current) == n:
nonlocal count
count += 1
if count == k:
nonlocal result
result = current
return
last_char = current[-1] if current else None
for c in 'abc':
if c != last_char:
backtrack(current + c)
if result:
return
count = 0
result = ''
backtrack('')
return result
print(getHappyString(3, 9)) # Output: "cab"public class HappyString {
private int count = 0;
private String result = "";
public String getHappyString(int n, int k) {
backtrack("", n, k);
return result;
}
private void backtrack(String current, int n, int k) {
if (current.length() == n) {
count++;
if (count == k) {
result = current;
}
return;
}
char lastChar = current.isEmpty() ? '0' : current.charAt(current.length() - 1);
for (char c : new char[]{'a', 'b', 'c'}) {
if (c != lastChar) {
backtrack(current + c, n, k);
if (count >= k) return; // Early termination
}
}
}
public static void main(String[] args) {
HappyString hs = new HappyString();
System.out.println(hs.getHappyString(3, 9)); // Output: "cab"
}
}#include <iostream>
#include <string>
using namespace std;
void backtrack(const string ¤t, int n, int k, int &count, string &result) {
if (current.length() == n) {
count++;
if (count == k) {
result = current;
}
return;
}
char lastChar = current.empty() ? '0' : current.back();
for (char c : "abc") {
if (c != lastChar) {
backtrack(current + c, n, k, count, result);
if (count >= k) return; // Early exit if we've found k-th string
}
}
}
string getHappyString(int n, int k) {
string result = "";
int count = 0;
backtrack("", n, k, count, result);
return result;
}
int main() {
cout << getHappyString(3, 9) << endl; // Output: "cab"
return 0;
}function getHappyString(n, k) {
let count = 0;
let result = "";
function backtrack(current) {
if (current.length === n) {
count++;
if (count === k) {
result = current;
}
return;
}
const lastChar = current[current.length - 1] || "";
for (const c of ['a', 'b', 'c']) {
if (c !== lastChar) {
backtrack(current + c);
if (result) return; // Early return when k-th string is found
}
}
}
backtrack("");
return result;
}
console.log(getHappyString(3, 9)); // Output: "cab"#include <stdio.h>
#include <string.h>
#define true 1
#define false 0
typedef int bool;
void generateHappyStrings(char *current, int n, int k, int *count, char *result) {
if (strlen(current) == n) {
(*count)++;
if (*count == k) {
strcpy(result, current);
}
return;
}
char lastChar = strlen(current) > 0 ? current[strlen(current) - 1] : '0';
for (char c = 'a'; c <= 'c'; c++) {
if (c != lastChar) {
char nextString[n + 1];
strcpy(nextString, current);
nextString[strlen(current)] = c;
nextString[strlen(current) + 1] = '\0';
generateHappyStrings(nextString, n, k, count, result);
if (*count >= k) return; // Early termination
}
}
}
char* getHappyString(int n, int k) {
char result[n + 1];
result[0] = '\0';
int count = 0;
char initial[1] = "";
generateHappyStrings(initial, n, k, &count, result);
if (count < k) return ""; // Less than k strings are possible
return strdup(result);
}
int main() {
printf("%s\n", getHappyString(3, 9)); // Output: "cab"
return 0;
}using System;
class HappyStringGenerator {
private int count = 0;
private string result = string.Empty;
public string GetHappyString(int n, int k) {
Backtrack(string.Empty, n, k);
return result;
}
private void Backtrack(string current, int n, int k) {
if (current.Length == n) {
count++;
if (count == k) {
result = current;
}
return;
}
char lastChar = current.Length > 0 ? current[current.Length - 1] : '\0';
foreach (char c in new char[] { 'a', 'b', 'c' }) {
if (c != lastChar) {
Backtrack(current + c, n, k);
if (count >= k) return; // Early termination once k-th is found
}
}
}
public static void Main() {
HappyStringGenerator generator = new HappyStringGenerator();
Console.WriteLine(generator.GetHappyString(3, 9)); // Output: "cab"
}
}In the Python solution, recursion is used within the backtrack function to construct strings while checking they remain happy. We maintain a count of happy strings as they are built and only capture the k-th when it is reached. If less than k happy strings exist, the result remains an empty string.
Time complexity is O(3^n), given the recursion depth potential. Space complexity is O(n) because of the recursion calls and temporary string lengths.
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.
from collections import deque
def getHappyString(n, k):
queue = deque(['a', 'b', 'c'])
count = 0
while queue:
current = queue.popleft()
if len(current) == n:
count += 1
if count == k:
return current
continue
last_char = current[-1]
for c in 'abc':
if c != last_char:
queue.append(current + c)
return "" # If k strings are not feasible
print(getHappyString(3, 9)) # Output: "cab"import java.util.LinkedList;
import java.util.Queue;
public class HappyStringIterative {
public String getHappyString(int n, int k) {
Queue<String> queue = new LinkedList<>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
int count = 0;
while (!queue.isEmpty()) {
String current = queue.poll();
if (current.length() == n) {
if (++count == k) return current;
continue;
}
char lastChar = current.charAt(current.length() - 1);
for (char c : new char[]{'a', 'b', 'c'}) {
if (c != lastChar) queue.offer(current + c);
}
}
return ""; // If k strings not found
}
public static void main(String[] args) {
HappyStringIterative hs = new HappyStringIterative();
System.out.println(hs.getHappyString(3, 9)); // Output: "cab"
}
}#include <iostream>
#include <queue>
#include <string>
using namespace std;
string getHappyString(int n, int k) {
queue<string> q;
q.push("a");
q.push("b");
q.push("c");
int count = 0;
while (!q.empty()) {
string current = q.front();
q.pop();
if (current.length() == n) {
if (++count == k) return current;
continue;
}
char lastChar = current[current.length() - 1];
for (char c : { 'a', 'b', 'c' }) {
if (c != lastChar) q.push(current + c);
}
}
return ""; // if less than k happy strings exist
}
int main() {
cout << getHappyString(3, 9) << endl; // Output: "cab"
return 0;
}function getHappyString(n, k) {
const queue = ['a', 'b', 'c'];
let count = 0;
while (queue.length > 0) {
const current = queue.shift();
if (current.length === n) {
if (++count === k) return current;
continue;
}
const lastChar = current[current.length - 1];
for (const c of ['a', 'b', 'c']) {
if (c !== lastChar) {
queue.push(current + c);
}
}
}
return ""; // If we can't form k strings
}
console.log(getHappyString(3, 9)); // Output: "cab"#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *cloneAndAppend(char *s, char c) {
int len = strlen(s);
char *newStr = malloc(len + 2);
strcpy(newStr, s);
newStr[len] = c;
newStr[len + 1] = '\0';
return newStr;
}
char* getHappyString(int n, int k) {
char *queue[59049]; // Max size when 3^10
char *initials[] = {"a", "b", "c"};
int front = 0, rear = 0, count = 0;
for (int i = 0; i < 3; ++i) {
queue[rear++] = initials[i];
}
while (front < rear) {
char *current = queue[front++];
if (strlen(current) == n) {
if (++count == k) {
return current;
}
free(current);
continue;
}
char lastChar = current[strlen(current) - 1];
for (char c = 'a'; c <= 'c'; c++) {
if (c != lastChar) {
queue[rear++] = cloneAndAppend(current, c);
}
}
free(current);
}
return ""; // If k strings are not possible
}
int main() {
printf("%s\n", getHappyString(3, 9)); // Output: "cab"
return 0;
}using System;
using System.Collections.Generic;
class HappyStringIterative {
public string GetHappyString(int n, int k) {
Queue<string> queue = new Queue<string>();
queue.Enqueue("a");
queue.Enqueue("b");
queue.Enqueue("c");
int count = 0;
while (queue.Count > 0) {
string current = queue.Dequeue();
if (current.Length == n) {
count++;
if (count == k) return current;
continue;
}
char lastChar = current[current.Length - 1];
foreach (char c in new char[] { 'a', 'b', 'c' }) {
if (c != lastChar) queue.Enqueue(current + c);
}
}
return ""; // If k strings aren't possible
}
public static void Main() {
HappyStringIterative hs = new HappyStringIterative();
Console.WriteLine(hs.GetHappyString(3, 9)); // Output: "cab"
}
}In Python's iteration-driven methodology, a deque (double-ended queue) is pivotal for symmetric string extensions from root sequences. Pushing the boundaries of each prefix by permissible extensions, full-length strings are acknowledged by incrementing an auxiliary counter. Functional string retrieval aligns with the k-th offering, punctuated with empty returns when insufficient quantities are calculated.
Time complexity is O(3^n), charting full paths through the construction. Space complexity is proportional at O(3^n), corresponding to queue state within the generative cycle.
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:
- If the length of the current string is equal to
n, add the current string to the answer arrayansand return; - If the length of the answer array is greater than or equal to
k, return directly; - Otherwise, we iterate over the character set
{a, b, c}. For each characterc, if the current string is empty or the last character of the current string is not equal toc, add the charactercto the current string, then recursively calldfs. 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.
function getHappyString(n: number, k: number): string {
const ans: string[] = [];
const s: string[] = [];
const dfs = () => {
if (s.length === n) {
ans.push(s.join(''));
return;
}
if (ans.length >= k) {
return;
}
for (const c of 'abc') {
if (!s.length || s.at(-1)! !== c) {
s.push(c);
dfs();
s.pop();
}
}
};
dfs();
return ans[k - 1] ?? '';
}func getHappyString(n int, k int) string {
ans := []string{}
var s []byte
var dfs func()
dfs = func() {
if len(s) == n {
ans = append(ans, string(s))
return
}
if len(ans) >= k {
return
}
for c := byte('a'); c <= 'c'; c++ {
if len(s) == 0 || s[len(s)-1] != c {
s = append(s, c)
dfs()
s = s[:len(s)-1]
}
}
}
dfs()
if len(ans) < k {
return ""
}
return ans[k-1]
}impl Solution {
pub fn get_happy_string(n: i32, k: i32) -> String {
let mut ans = Vec::new();
let mut s = String::new();
let mut k = k;
fn dfs(n: i32, s: &mut String, ans: &mut Vec<String>, k: &mut i32) {
if s.len() == n as usize {
ans.push(s.clone());
return;
}
if ans.len() >= *k as usize {
return;
}
for c in "abc".chars() {
if s.is_empty() || s.chars().last() != Some(c) {
s.push(c);
dfs(n, s, ans, k);
s.pop();
}
}
}
dfs(n, &mut s, &mut ans, &mut k);
if ans.len() < k as usize {
"".to_string()
} else {
ans[(k - 1) as usize].clone()
}
}
}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.
function getHappyString(n: number, k: number): string {
if (k > 3 * (1 << (n - 1))) {
return '';
}
const cs = 'abc';
const ans: string[] = [];
for (let i = 0; i < n; i++) {
const remain = 1 << (n - i - 1);
for (const c of cs) {
if (ans.at(-1) === c) {
continue;
}
if (k <= remain) {
ans.push(c);
break;
}
k -= remain;
}
}
return ans.join('');
}func getHappyString(n int, k int) string {
if k > 3*(1<<(n-1)) {
return ""
}
cs := "abc"
ans := make([]byte, 0, n)
for i := 0; i < n; i++ {
remain := 1 << (n - i - 1)
for j := 0; j < len(cs); j++ {
c := cs[j]
if len(ans) > 0 && ans[len(ans)-1] == c {
continue
}
if k <= remain {
ans = append(ans, c)
break
}
k -= remain
}
}
return string(ans)
}impl Solution {
pub fn get_happy_string(n: i32, mut k: i32) -> String {
if k > 3 * (1 << (n - 1)) {
return String::new();
}
let cs = ['a', 'b', 'c'];
let mut ans: Vec<char> = Vec::with_capacity(n as usize);
for i in 0..n {
let remain = 1 << (n - i - 1);
for &c in &cs {
if !ans.is_empty() && *ans.last().unwrap() == c {
continue;
}
if k <= remain {
ans.push(c);
break;
}
k -= remain;
}
}
ans.into_iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time complexity is |
| Iterative Enumeration | Time complexity is |
| DFS | – |
| Mathematics | – |
Complexity analysis
| 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 |
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.