LeetCode #1415 — MEDIUM

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

Move from brute-force thinking to an efficient approach using backtracking strategy.

The 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 9^th string = "cab"

Constraints:

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

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Backtracking

Example 1

1
3

Example 2

1
4

Example 3

3
9

Step 02

Core Insight

What unlocks the optimal approach

Generate recursively all the happy strings of length n.
Sort them in lexicographical order and return the kth string if it exists.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1415: The k-th Lexicographical String of All Happy Strings of Length n
class Solution {
    private List<String> ans = new ArrayList<>();
    private StringBuilder s = new StringBuilder();
    private int n, k;

    public String getHappyString(int n, int k) {
        this.n = n;
        this.k = k;
        dfs();
        return ans.size() < k ? "" : ans.get(k - 1);
    }

    private void dfs() {
        if (s.length() == n) {
            ans.add(s.toString());
            return;
        }
        if (ans.size() >= k) {
            return;
        }
        for (char c : "abc".toCharArray()) {
            if (s.isEmpty() || s.charAt(s.length() - 1) != c) {
                s.append(c);
                dfs();
                s.deleteCharAt(s.length() - 1);
            }
        }
    }
}

// Accepted solution for LeetCode #1415: The k-th Lexicographical String of All Happy Strings of Length n
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]
}

# Accepted solution for LeetCode #1415: The k-th Lexicographical String of All Happy Strings of Length n
class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        def dfs():
            if len(s) == n:
                ans.append("".join(s))
                return
            if len(ans) >= k:
                return
            for c in "abc":
                if not s or s[-1] != c:
                    s.append(c)
                    dfs()
                    s.pop()

        ans = []
        s = []
        dfs()
        return "" if len(ans) < k else ans[k - 1]

// Accepted solution for LeetCode #1415: The k-th Lexicographical String of All Happy Strings of Length n
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()
        }
    }
}

// Accepted solution for LeetCode #1415: The k-th Lexicographical String of All Happy Strings of Length n
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] ?? '';
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n × 2^n)

Space

O(n)

Approach Breakdown

EXHAUSTIVE

O(nⁿ) time

O(n) space

Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.

BACKTRACKING + PRUNING

O(n!) time

O(n) space

Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).

Shortcut: Backtracking time = size of the pruned search tree. Focus on proving your pruning eliminates most branches.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Missing undo step on backtrack

Wrong move: Mutable state leaks between branches.

Usually fails on: Later branches inherit selections from earlier branches.

Fix: Always revert state changes immediately after recursive call.