LeetCode Entry

1096. Brace Expansion II

25.09.2026 hard 2026 kotlin rust

Expand sets-expression {x,y}z

1096. Brace Expansion II hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1493

Problem TLDR

Expand sets-expression {x,y}z

Intuition

Parse recursively like a math expression, treating ‘,’ as plus and ‘{‘ as a multiplication. Another way - expand inner-most braces recursively.

Approach

• regex for innermost is group no containing braces “{[^{}]+}”
• or find the leftmost ‘}’ and rightmost ‘{‘ before it

Complexity

• Time complexity: \(O(n^2 3^n/3 log(n))\)

• Space complexity: \(O(N)\)

Code

    fun braceExpansionII(e: String): List<String> =
        Regex("""\{([^{}]+)\}""").find(e)?.run {
            groupValues[1].split(',').flatMap {
                braceExpansionII(e.replaceRange(range, it)) }.toSet().sorted()
        } ?: listOf(e)

    pub fn brace_expansion_ii(e: String) -> Vec<String> {
        let Some(r) = e.find('}') else { return vec![e] };
        let l = e[..r].rfind('{').unwrap();
        e[l+1..r].split(',')
            .flat_map(|w| Self::brace_expansion_ii([&e[..l], w, &e[r+1..]].concat()))
            .sorted().dedup().collect()
    }