The k-th Happy String of Length n: Backtracking with Pruning

A "happy string" is a string that only contains the letters 'a', 'b', and 'c', and no two adjacent characters are the same. Given two integers n and k, return the k-th happy string of length n in lexicographical order. If there are fewer than k happy strings of length n, return an empty string "".

This is LeetCode 1415: The k-th Lexicographical String of All Happy Strings of Length n. For example, with n = 3 and k = 9, the sorted list of all happy strings of length 3 is ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"], so the answer is "cab".

Why this problem matters

This problem is a clean distillation of constrained backtracking with early termination. You are generating strings character by character, but with a rule that limits your choices at each position. On top of that, you do not need all the results. You only need the k-th one, which means you can stop as soon as you find it.

Interviewers like this problem because it tests two skills at once. First, can you set up a backtracking solution that respects a constraint (no repeated adjacent characters)? Second, can you count completions and bail out early instead of generating everything? If you can do both, you are demonstrating real command of the backtracking pattern.

The structure also maps directly to many real-world enumeration tasks: generating passwords with constraints, building valid configurations, or listing sequences that satisfy some invariant.

The key insight

You can generate happy strings in lexicographical order by always trying 'a', 'b', 'c' in that order at each position, and skipping any letter that matches the previous character. Since we try letters alphabetically and recurse depth-first, completed strings naturally come out sorted.

The second insight is that you do not need to store all the strings. You just keep a counter. Every time you complete a string of length n, you decrement k. When k reaches zero, you have found the answer. Return it immediately and let the backtracking unwind. Any strings you have not yet generated are simply never built.

This means the algorithm does O(k * n) work in the worst case, not O(total_happy_strings * n). For small k relative to the total, the savings are significant.

The solution

def getHappyString(n: int, k: int) -> str:
    result = []
    count = [0]

    def backtrack(path):
        if len(path) == n:
            count[0] += 1
            if count[0] == k:
                result.append("".join(path))
            return

        for ch in "abc":
            if path and path[-1] == ch:
                continue
            path.append(ch)
            backtrack(path)
            if result:
                return
            path.pop()

    backtrack([])
    return result[0] if result else ""

The function builds strings using a list called path. At each position, it loops through 'a', 'b', 'c' in order. If the candidate character matches the last character in path, it skips that character. This single check enforces the "no adjacent duplicates" constraint.

When path reaches length n, we have a complete happy string. We increment the counter. If the counter equals k, we save the result. On the way back up, every recursive call checks whether result is non-empty. If it is, we return immediately without exploring further branches.

The path list is mutated in place with append and pop, following the standard choose-explore-unchoose pattern. This avoids creating new string objects at every level of recursion.

Visual walkthrough

Let's trace the algorithm for n = 3 and k = 9. The answer should be "cab". Watch how the algorithm counts completed strings and stops the moment it hits the 9th one.

The algorithm generates exactly 9 strings and stops. It never touches "cac", "cba", or "cbc". The deeper into the tree the answer is, the more work you do, but you never do more work than necessary.

Complexity analysis

Time: Each happy string takes O(n) to build (one character per level of recursion). We build at most k strings before stopping. So the total work is O(k * n). In the worst case where k equals the total number of happy strings (3 * 2^(n-1)), this becomes O(n * 2^n), but the early termination makes the average case much better.

Space: The recursion goes n levels deep, and the path list holds at most n characters. So the space usage is O(n). We do not store all the happy strings, just the one we are looking for.

The building blocks

1. Constrained generation with backtracking

The core template here is the same one you see in Generate Parentheses, Permutations, and Combination Sum:

def backtrack(state):
    if is_complete(state):
        record(state)
        return

    for choice in valid_choices(state):
        apply(choice)
        backtrack(state)
        undo(choice)

In this problem, valid_choices means "letters from that do not match the last character." is_complete means the path has length n. apply is path.append(ch) and undo is path.pop().

The constraint (no adjacent duplicates) determines which branches you explore. The template stays the same across dozens of problems. Only the constraint changes.

2. Early termination by counting

When you do not need all results, you can add a counter that tracks how many complete solutions you have seen. Once the counter matches your target, you save the answer and propagate a "stop" signal back through the recursion.

In this solution, the stop signal is if result: return. Other implementations use a boolean flag, or decrement k and check for zero, or raise an exception. The mechanism does not matter. The idea is that you short-circuit the remaining branches.

This pattern applies to problems like "find the k-th permutation," "find the k-th smallest element in a sorted matrix," or any problem that asks for a specific item from an ordered enumeration.

Edge cases

Before submitting, verify these:

• k is larger than total count: For length n, there are exactly 3 * 2^(n-1) happy strings. If k exceeds that, return "". The algorithm handles this naturally: it finishes without ever setting a result.
• n = 1: The only happy strings are "a", "b", "c". So k must be 1, 2, or 3. The constraint check (path[-1] == ch) is skipped because path is empty at the first position.
• k = 1: Always returns "a" * n alternating with "b". For n = 1 it is "a", for n = 2 it is "ab", for n = 3 it is "aba". The very first path through the tree.
• Large n with small k: Even with n = 10 (total 1536 strings), if k = 1, the algorithm does only 10 recursive calls. The early exit makes it fast.

From understanding to recall

You can see the backtracking tree. You understand the constraint: skip any letter that matches the previous one. You know the early termination trick: count completions and bail when you hit k. But can you write this from scratch in two minutes without checking your notes?

Under interview conditions, people forget small details. They write if path[-1] == ch but crash on an empty path. They forget to pop after the recursive call. They generate all strings and then index into the list, missing the early termination optimization entirely.

Spaced repetition closes that gap. You write the constrained backtracking template, the constraint check, and the counting trick from memory at increasing intervals. After a few rounds, the code flows out automatically. You see "k-th happy string" and you know exactly what to write.

This problem combines two building blocks that appear across many LeetCode problems: constrained generation and early termination. Learning them independently and drilling them with spaced repetition is far more effective than solving dozens of similar problems and hoping the patterns stick.

Related posts

• Permutations - Another constrained generation problem. Each element is used exactly once, while happy strings allow reuse with an adjacency constraint. Compare how the "valid choices" differ between the two.
• Generate Parentheses - Uses the same backtracking template with a different constraint (open/close counters instead of adjacency). Both problems prune the search tree during construction, not after.
• Letter Combinations of a Phone Number - Generates strings character by character from a set of choices. No adjacency constraint, but the same recursive structure. Adding a constraint to that template gives you this problem.

CodeBricks breaks the k-th happy string into its constrained backtracking and early termination building blocks, then drills them independently with spaced repetition. You type the constraint check and the counting logic from scratch until they are automatic. When a backtracking problem shows up in your interview, you do not think about it. You just write it.