LeetCode 1415 – The K-th Lexicographical String of All Happy Strings of Length n

In this article we will explain LeetCode 1415 in a very intuitive way. We will understand:

• What is a Happy String
• How Lexicographical Order works
• Backtracking solution with recursion tree
• Java implementation
• Time and space complexity
• Alternative approaches

---

What is a Happy String?

A happy string is a string that satisfies two conditions:

• It contains only characters a, b, c
• No two adjacent characters are the same

Example

Valid Happy Strings

ab
ac
ba
bc
ca
cb

Invalid Strings

aa
bb
cc

Because adjacent characters are repeated. ---

Problem Statement

Given two integers:

• n → length of string
• k → position in lexicographical order

Return the k-th happy string of length n.

If fewer than k happy strings exist → return an empty string.

---

Example

Input:
n = 3
k = 9

Output:
cab

---

Step 1 — Generate Happy Strings

We build strings using characters:

a, b, c

But we cannot repeat adjacent characters. ---

Recursion Tree Visualization

                 ""
          /       |       \
        a         b        c
      /   \     /   \    /   \
    ab     ac  ba    bc ca    cb
   / \    / \  / \   / \ / \   / \
 aba abc aca acb bab bac bca bcb cab cac cba cbc

Each level increases the string length. ---

Lexicographical Order

All happy strings of length 3:

1  aba
2  abc
3  aca
4  acb
5  bab
6  bac
7  bca
8  bcb
9  cab
10 cac
11 cba
12 cbc

Since:

k = 9

Answer:

cab

---

Backtracking Intuition

We generate strings using DFS. Rules:

• Add characters one by one
• Skip if same as previous character
• Stop once we reach k strings

---

Java Backtracking Solution

class Solution {

    int count = 0;
    String result = "";

    public String getHappyString(int n, int k) {
        dfs("", n, k);
        return result;
    }

    private void dfs(String curr, int n, int k) {

        if(curr.length() == n){
            count++;

            if(count == k){
                result = curr;
            }
            return;
        }

        for(char c : new char[]{'a','b','c'}){

            if(curr.length() > 0 && curr.charAt(curr.length()-1) == c)
                continue;

            dfs(curr + c, n, k);

            if(!result.equals("")) return;
        }
    }
}

---

Time Complexity

Total happy strings:

3 × 2^(n-1)

Time Complexity:

O(2^n)

Space Complexity:

O(n)

Due to recursion stack. ---

Alternative Approaches

Approach	Time	Space	Difficulty
Backtracking	O(2^n)	O(n)	Easy
Greedy Mathematical	O(n)	O(1)	Hard
BFS Generation	O(2^n)	O(2^n)	Easy

---

Greedy Optimization Idea

Instead of generating all strings:

blockSize = 2^(remaining_length)

Example:

n = 3
Each starting character produces 4 strings

a → 4
b → 4
c → 4

If:

k = 9

Skip first 8 strings → answer starts with:

c

This allows solving in **O(n)** time. ---

Key Takeaways

• Understand lexicographical ordering
• Use backtracking to generate valid strings
• Stop early once kth string is found
• Greedy math approach improves performance

---

Conclusion

LeetCode 1415 is a great problem to practice backtracking and recursion tree thinking. Understanding how to generate valid strings and control search space is a common coding interview skill.