LeetCode Entry

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

14.03.2026 medium 2026 kotlin rust

K-th generated abc non-repeating string

1415. The k-th Lexicographical String of All Happy Strings of Length n medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1297

Problem TLDR

K-th generated abc non-repeating string #medium #dfs

Intuition

    // the problem is small, just generate all, sort
    // abab
    // abac
    // abca
    // abcb
    // acab
    // acac
    // baba
    // 2^10

The simple solution: just generate all strings in DFS, sort.

Approach

• the DFS already generates in a sorted order, no need to sort
• no need to keep strings, just count until k
• the math intuition: each char generates subtree with known elements count, initial a: 2^(n-1), b: 2^(n-1), c: 2^(n-1)
• index is “abc”[k/count] at first, then {“ab”, “bc”, “ac”}[k/count], k %= count, count /= 2

Complexity

• Time complexity: \(O(2^n)\), or O(n)

• Space complexity: \(O(2^n)\), or O(1)

Code

// 11ms
    fun getHappyString(n: Int, k: Int, s: String = "abc", b: Int = 1 shl n-1): String =
        if (n==0 || (k-1)/b > s.lastIndex) "" else
        s[(k-1)/b] + getHappyString(n-1, (k-1)%b+1, "abc".replace(""+s[(k-1)/b],""))

// 12ms
    pub fn get_happy_string(n: i32, k: i32) -> String {
        (0..n).map(|_| *b"abc").multi_cartesian_product()
        .filter(|s| s.windows(2).all(|w| w[0] != w[1]))
        .nth(k as usize-1).and_then(|v| String::from_utf8(v).ok()).unwrap_or_default()
    }