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

The problem asks us to generate strings of length n using only the characters 'a', 'b', and 'c', with one important rest

leetcodemediumstringbacktracking

LeetCode Problem 1415

Difficulty: 🟡 Medium
Topics: String, Backtracking

Solution

LeetCode 1415, The k-th Lexicographical String of All Happy Strings of Length n

Problem Understanding

The problem asks us to generate strings of length n using only the characters 'a', 'b', and 'c', with one important restriction: no two adjacent characters can be the same. These valid strings are called happy strings.

After generating all valid happy strings of length n, we sort them in lexicographical order, then return the kth string in that ordering. If fewer than k happy strings exist, we return an empty string.

A lexicographical ordering is the same ordering used in a dictionary. For example:

"aba" < "abc" < "aca"

because comparison happens character by character from left to right.

The input consists of two integers:

  • n, the desired length of the happy strings
  • k, the 1-indexed position of the string we want after sorting

The constraints are relatively small:

1 <= n <= 10
1 <= k <= 100

These limits are important because they tell us the total number of possible strings is manageable. In fact:

  • The first character has 3 choices
  • Every later character has 2 choices, because it cannot equal the previous character

So the total number of happy strings of length n is:

$$3 \times 2^{n-1}$$

For n = 10, this becomes:

$$3 \times 2^9 = 1536$$

This is small enough that generating all valid strings is completely feasible.

Several edge cases are important:

  • If k is larger than the number of happy strings, we must return ""
  • For n = 1, every single character string is valid
  • Lexicographical order matters, so generation order must be carefully controlled
  • Adjacent duplicates such as "aa" or "bcc" are invalid and must never be generated

Approaches

Brute Force Approach

A brute force solution would generate every possible string of length n using the characters 'a', 'b', and 'c'.

Since each position has 3 choices, there are:

$$3^n$$

possible strings.

For every generated string, we would check whether adjacent characters are different. If valid, we would add it to a list. After generating all possibilities, we would sort the valid strings lexicographically and return the kth one if it exists.

This approach is correct because it exhaustively checks every candidate string. However, it performs unnecessary work because most generated strings may be invalid.

For example, when n = 10, brute force generates:

$$3^{10} = 59049$$

strings, even though only 1536 are valid happy strings.

Optimal Approach

The better solution uses backtracking.

Instead of generating all possible strings and filtering afterward, we build only valid strings from the beginning.

At every step:

  • Try adding 'a', 'b', or 'c'
  • Skip any character equal to the previous character
  • Continue recursively until the string length becomes n

Because we try characters in sorted order:

'a' -> 'b' -> 'c'

the generated strings automatically appear in lexicographical order.

We can stop immediately once we generate the kth happy string, which avoids unnecessary computation.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n * n) O(3^n * n) Generates every possible string, then filters
Optimal O(2^n) O(n) Generates only valid strings using backtracking

Algorithm Walkthrough

Step 1: Initialize Storage

We maintain:

  • A list to store generated happy strings
  • A mutable path representing the current string being built

The path grows and shrinks during recursion.

Step 2: Start Backtracking

We recursively build the string character by character.

At each recursion level:

  • If the current path length equals n, we formed a complete happy string
  • Add it to the result list
  • Return to explore other possibilities

Step 3: Try Characters in Lexicographical Order

For every position, try:

'a', 'b', 'c'

in that exact order.

This guarantees generated strings are already lexicographically sorted.

Step 4: Enforce the Happy String Rule

Before adding a character:

  • If the path is not empty
  • And the new character equals the last character

skip that choice.

This ensures no adjacent characters are identical.

Step 5: Recurse

After choosing a valid character:

  • Append it to the path
  • Recursively continue building the string
  • Remove the character afterward to backtrack

This explores all valid possibilities.

Step 6: Return the k-th String

After generation:

  • If fewer than k strings exist, return ""
  • Otherwise return result[k - 1]

The subtraction by one is necessary because lists use zero-based indexing while the problem uses one-based indexing.

Why it works

The algorithm always maintains the invariant that the current partial string is valid. Since invalid states are never explored, every completed string is guaranteed to be a happy string.

Because characters are explored in lexicographical order at every position, the final generated sequence is automatically sorted lexicographically. Therefore, the kth generated string is exactly the kth lexicographical happy string.

Python Solution

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        result = []
        path = []

        def backtrack() -> None:
            if len(path) == n:
                result.append("".join(path))
                return

            for char in "abc":
                if path and path[-1] == char:
                    continue

                path.append(char)
                backtrack()
                path.pop()

        backtrack()

        if k > len(result):
            return ""

        return result[k - 1]

The implementation follows the exact recursive structure described earlier.

The path list stores the current string under construction. Using a list instead of repeated string concatenation is more efficient because lists are mutable.

The backtrack function recursively explores all valid continuations.

The base case occurs when:

len(path) == n

At that moment, we formed a complete happy string, so we join the characters and append the result.

The loop iterates through "abc" in sorted order. This guarantees lexicographical ordering automatically.

The condition:

if path and path[-1] == char:

prevents adjacent duplicate characters.

After recursion returns, path.pop() removes the last character so the algorithm can try another branch. This is the essence of backtracking.

Finally, we verify whether the requested kth string exists before returning it.

Go Solution

func getHappyString(n int, k int) string {
    result := []string{}
    path := []byte{}

    var backtrack func()

    backtrack = func() {
        if len(path) == n {
            result = append(result, string(path))
            return
        }

        for _, char := range []byte{'a', 'b', 'c'} {
            if len(path) > 0 && path[len(path)-1] == char {
                continue
            }

            path = append(path, char)
            backtrack()
            path = path[:len(path)-1]
        }
    }

    backtrack()

    if k > len(result) {
        return ""
    }

    return result[k-1]
}

The Go implementation mirrors the Python version closely.

Instead of using Python lists and strings, Go uses a []byte slice for the current path. This is efficient because bytes are mutable and easy to append and remove during recursion.

Backtracking is implemented using slice resizing:

path = path[:len(path)-1]

Go does not support nested named functions in the same way Python does, so we declare a function variable first:

var backtrack func()

then assign the recursive function to it.

Returning an empty string is straightforward because Go strings default naturally to "".

Worked Examples

Example 1

Input: n = 1, k = 3

Generated happy strings:

Step Current String
1 "a"
2 "b"
3 "c"

The 3rd string is:

"c"

Output:

"c"

Example 2

Input: n = 1, k = 4

Generated strings:

Index String
1 "a"
2 "b"
3 "c"

Only 3 happy strings exist.

Since:

k = 4

the answer does not exist.

Output:

""

Example 3

Input: n = 3, k = 9

Backtracking generates strings in this order:

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

The 9th string is:

"cab"

Output:

"cab"

Complexity Analysis

Measure Complexity Explanation
Time O(2^n) Each position after the first has 2 valid choices
Space O(n) Recursive depth and current path storage

The total number of valid happy strings is:

$$3 \times 2^{n-1}$$

The algorithm explores each valid string exactly once. Since invalid states are pruned immediately, the runtime depends on the number of valid happy strings rather than all possible strings.

The recursion depth never exceeds n, so auxiliary space is linear.

Test Cases

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        result = []
        path = []

        def backtrack():
            if len(path) == n:
                result.append("".join(path))
                return

            for char in "abc":
                if path and path[-1] == char:
                    continue

                path.append(char)
                backtrack()
                path.pop()

        backtrack()

        if k > len(result):
            return ""

        return result[k - 1]

sol = Solution()

assert sol.getHappyString(1, 1) == "a"      # first single-character string
assert sol.getHappyString(1, 2) == "b"      # second single-character string
assert sol.getHappyString(1, 3) == "c"      # third single-character string
assert sol.getHappyString(1, 4) == ""       # k exceeds total strings

assert sol.getHappyString(3, 1) == "aba"    # first lexicographical length-3 string
assert sol.getHappyString(3, 9) == "cab"    # provided example
assert sol.getHappyString(3, 12) == "cbc"   # last valid length-3 string
assert sol.getHappyString(3, 13) == ""      # beyond total count

assert sol.getHappyString(2, 1) == "ab"     # smallest length-2 string
assert sol.getHappyString(2, 6) == "cb"     # last length-2 string

assert sol.getHappyString(10, 1) != ""      # large n boundary
assert sol.getHappyString(10, 100) != ""    # larger k within range

Test Summary

Test Why
n=1, k=1 Smallest possible valid input
n=1, k=4 k exceeds total strings
n=3, k=9 Verifies provided example
n=3, k=12 Checks final valid string
n=3, k=13 Checks out-of-range behavior
n=2, k=1 Verifies lexicographical ordering
n=2, k=6 Verifies last string generation
n=10, k=100 Stress test near upper constraints

Edge Cases

One important edge case occurs when k exceeds the total number of happy strings. A buggy implementation might attempt to access an invalid index and crash. This solution avoids that by explicitly checking:

if k > len(result):
    return ""

before indexing into the result list.

Another important case is n = 1. Since there are no adjacent characters, every single-character string is automatically valid. Some implementations accidentally apply adjacency checks incorrectly and reject valid single-character strings. Here, the condition:

if path and path[-1] == char:

only runs when the path is non-empty, so length-1 strings work correctly.

A third important edge case involves lexicographical ordering. If characters are explored in arbitrary order, the generated strings may not match dictionary ordering, causing the wrong answer to be returned for a given k. This implementation guarantees correctness by always iterating through characters in the order:

"a", "b", "c"

during recursion.

Another subtle case is proper backtracking cleanup. Forgetting to remove characters after recursion causes future recursive branches to inherit incorrect state. The explicit path.pop() operation ensures every recursive call restores the path exactly to its previous state before exploring another branch.