1096. Brace Expansion II - Solution & Explanation

Q: Is Brace Expansion II easy or hard?

Brace Expansion II is classified as a Hard problem because it combines parsing, recursion, and set-based combination logic. Handling nested braces, union operations, and concatenation correctly requires careful expression evaluation design.

Q: Brace Expansion II Python/Java solution

Python solutions usually implement recursive DFS parsing with sets and string concatenation. Java solutions often use iterative stack-based parsing with HashSet structures to track partial expansions. Both approaches run in roughly O(n * k) time.

Q: How to solve Brace Expansion II in O(n)?

A strict O(n) solution is not possible because the algorithm must generate every expanded string. The best achievable complexity is proportional to the output size, typically O(n * k). Efficient implementations minimize overhead by using sets and combining partial results only when necessary.

Q: What is the best approach for Brace Expansion II?

Depth-first parsing with backtracking is the most common approach. It treats the expression like a grammar with union and concatenation operations and recursively evaluates nested braces. Using sets ensures duplicates are removed automatically. The time complexity is roughly O(n * k), where k is the number of generated strings.

Q: Is Brace Expansion II asked at Google/Amazon/Meta?

Brace-style parsing problems appear in interviews at companies like Google and Amazon because they test recursion, parsing, and data structure usage. Variations of expression parsing and grammar evaluation are common system and algorithm interview topics.

Q: What data structure is used in Brace Expansion II?

Typical implementations use sets to store unique intermediate strings and either recursion or stacks to manage nested braces. Stacks help evaluate expressions iteratively, while recursion naturally handles nested parsing structures.

Q: What is the time complexity of Brace Expansion II?

The time complexity is O(n * k), where n is the length of the expression and k is the total number of generated output strings. Each expansion step may combine sets of strings using Cartesian products. The space complexity is also O(n * k) because all generated strings must be stored.

The problem

Under the grammar given below, strings can represent a set of lowercase words. Let R(expr) denote the set of words the expression represents.

The grammar can best be understood through simple examples:

Single letters represent a singleton set containing that word.
- R("a") = {"a"}
- R("w") = {"w"}
When we take a comma-delimited list of two or more expressions, we take the union of possibilities.
- R("{a,b,c}") = {"a","b","c"}
- R("{{a,b},{b,c}}") = {"a","b","c"} (notice the final set only contains each word at most once)
When we concatenate two expressions, we take the set of possible concatenations between two words where the first word comes from the first expression and the second word comes from the second expression.
- R("{a,b}{c,d}") = {"ac","ad","bc","bd"}
- R("a{b,c}{d,e}f{g,h}") = {"abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"}

Formally, the three rules for our grammar:

For every lowercase letter x, we have R(x) = {x}.
For expressions e₁, e₂, ... , e_k with k >= 2, we have R({e₁, e₂, ...}) = R(e₁) ∪ R(e₂) ∪ ...
For expressions e₁ and e₂, we have R(e₁ + e₂) = {a + b for (a, b) in R(e₁) × R(e₂)}, where + denotes concatenation, and × denotes the cartesian product.

Given an expression representing a set of words under the given grammar, return the sorted list of words that the expression represents.

Example 1:

Input: expression = "{a,b}{c,{d,e}}"
Output: ["ac","ad","ae","bc","bd","be"]

Example 2:

Input: expression = "{{a,z},a{b,c},{ab,z}}"
Output: ["a","ab","ac","z"]
Explanation: Each distinct word is written only once in the final answer.

Constraints:

1 <= expression.length <= 60
expression[i] consists of '{', '}', ','or lowercase English letters.
The given expression represents a set of words based on the grammar given in the description.

Approach overview

Problem Overview: You are given a string expression that contains lowercase letters, commas, and curly braces. Braces represent union operations while adjacent expressions represent concatenation. The task is to expand the expression and return all possible strings in sorted order without duplicates.

Approach 1: Depth-First Parsing with Backtracking (O(n * k) time, O(n * k) space)

This approach recursively parses the expression and builds results using set operations. Treat commas as union and adjacency as concatenation. During parsing, maintain a current set of strings and combine it with the next parsed component using Cartesian product logic. When encountering a {, recursively evaluate until the matching }, then merge the results. Sets automatically remove duplicates and make union operations straightforward.

The key insight is that brace expressions behave like a small grammar: union (comma) and concatenation (adjacent tokens). DFS naturally models this structure because nested braces become recursive calls. This method is clean and easy to reason about, especially when implementing with backtracking and recursive string parsing.

Approach 2: Iterative Stack-Based Expression Evaluation (O(n * k) time, O(n * k) space)

This method evaluates the expression iteratively using stacks, similar to parsing arithmetic expressions. Maintain stacks for intermediate result sets and operators. When encountering letters, push them as singleton sets. When encountering {, start a new evaluation frame. Commas represent union operations while adjacency triggers concatenation between the top sets.

When } appears, resolve all operations inside that brace level and push the combined result back to the previous frame. Concatenation is handled by generating the product of two sets, while union merges them. Using stacks avoids recursion depth issues and mirrors classic expression parsing patterns. The approach relies heavily on a stack to track nested scopes and operators.

Recommended for interviews: The depth-first parsing approach is usually preferred. It clearly models the grammar of brace expressions and demonstrates strong recursion and parsing skills. Interviewers expect candidates to recognize union vs concatenation and handle nested braces correctly. The stack-based solution shows deeper knowledge of expression evaluation and is useful if you want to avoid recursion or demonstrate iterative parsing techniques.

Approach 1: Depth-First Parsing Approach

This approach involves parsing the expression recursively. By evaluating the expression in a depth-first manner, you can handle nested structures and perform set operations (union and Cartesian product) to build up the set of possible words.

Use a recursive function to handle expressions within braces and different operations between them.

Python

def brace_expansion_ii(expression):
    def evaluate(expr):
        stack = []
        cur_set = set()
        i, n = 0, len(expr)
        while i < n:
            if expr[i] == '{':
                # Find the matching closing brace
                j, depth = i, 0
                while j < n:
                    if expr[j] == '{':
                        depth += 1
                    elif expr[j] == '}':
                        depth -= 1
                    if depth == 0:
                        break
                    j += 1
                # Current set exploration
                cur_set = cur_set.union(evaluate(expr[i + 1:j]))
                i = j
            elif expr[i] == ',':
                stack.append(cur_set)
                cur_set = set()
            else:
                j = i + 1
                while j < n and expr[j].isalpha():
                    j += 1
                cur_set = {expr[i:j]} if not cur_set else {x + expr[i:j] for x in cur_set}
                i = j - 1
            i += 1
        result = set()
        while stack:
            result = result.union(stack.pop())
        result = result.union(cur_set)
        return result

    return sorted(evaluate(expression))

# Example usage:
expression = "{a,b}{c,{d,e}}"
print(brace_expansion_ii(expression))

JavaScript

function braceExpansionII(expression) {
    const evaluate = (expr) => {
        let stack = [], currentSet = new Set(), i = 0;
        while (i < expr.length) {
            if (expr[i] === '{') {
                let j = i, depth = 0;
                while (j < expr.length) {
                    if (expr[j] === '{') depth++;
                    if (expr[j] === '}') depth--;
                    if (depth === 0) break;
                    j++;
                }
                const partSet = evaluate(expr.substring(i + 1, j));
                const newSet = new Set();
                currentSet.forEach(prefix => {
                    partSet.forEach(part => {
                        newSet.add(prefix + part);
                    });
                });
                currentSet = newSet.size ? newSet : partSet;
                i = j;
            } else if (expr[i] === ',') {
                stack.push(currentSet);
                currentSet = new Set();
            } else {
                let j = i + 1;
                while (j < expr.length && /[a-z]/.test(expr[j])) j++;
                const term = expr.slice(i, j);
                const newSet = new Set();
                currentSet.forEach(prefix => newSet.add(prefix + term));
                currentSet = newSet.size ? newSet : new Set([term]);
                i = j - 1;
            }
            i++;
        }
        while (stack.length) {
            stack.pop().forEach(item => currentSet.add(item));
        }
        return currentSet;
    };

    return Array.from(evaluate(expression)).sort();
}

// Example usage:
let expression = "{a,b}{c,{d,e}}";
console.log(braceExpansionII(expression));

This Python solution uses a recursive helper function evaluate that processes the input string based on parsing depth-first manner using a stack. The function finds and processes sub-expressions recursively. It performs set operations—union and concatenation—to evaluate the possible sets resulting from the input expression.

Complexity

Time Complexity: O(n^k) in the worst case, where n is the length of the expression and k is the number of nested braces and operations.
Space Complexity: O(n^k), due to multiple recursive calls and storage of intermediate results in sets.

Try this approach in the editor

Approach 2: Iterative Stack-Based Approach

This approach uses an explicit stack to manage operations iteratively. The expression is parsed character by character, pushing operations and sets onto the stack for processing in the correct order. This method harnesses the stack data structure to avoid recursion, primarily controlling the flow with loops and stack manipulation.

Java

import java.util.*;

public class BraceExpansionII {
    public static List<String> braceExpansionII(String expression) {
        Deque<Character> opStack = new ArrayDeque<>();
        Deque<Set<String>> setStack = new ArrayDeque<>();
        Set<String> currentSet = new HashSet<>();
        currentSet.add("");  // Base for concatenations
        int i = 0;

        while (i < expression.length()) {
            char ch = expression.charAt(i);
            if (ch == '{') {
                opStack.push(ch);
                i++;
            } else if (ch == '}') {
                Set<String> tempSet = new HashSet<>();
                while (!opStack.isEmpty() && opStack.peek() != '{') {
                    opStack.pop();  // Pop ','
                    tempSet.addAll(currentSet);
                    currentSet = setStack.pop();
                }
                opStack.pop();  // Pop '{'
                currentSet.addAll(tempSet);
                i++;
            } else if (ch == ',') {
                setStack.push(new HashSet<>(currentSet));
                currentSet.clear();
                opStack.push(ch);
                i++;
            } else {
                // Handling a letter or sequence of letters
                int j = i;
                while (j < expression.length() && Character.isLetter(expression.charAt(j))) {
                    j++;
                }
                String subExpr = expression.substring(i, j);
                Set<String> newSet = new HashSet<>();
                for (String prefix : currentSet) {
                    newSet.add(prefix + subExpr);
                }
                currentSet = newSet;
                i = j;
            }
        }

        while (!setStack.isEmpty()) {
            currentSet.addAll(setStack.pop());
        }

        List<String> result = new ArrayList<>(currentSet);
        Collections.sort(result);
        return result;
    }

    public static void main(String[] args) {
        String expression = "{{a,z},a{b,c},{ab,z}}";
        System.out.println(braceExpansionII(expression));
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

public class BraceExpansionII {
    public IList<string> BraceExpansionII(string expression) {
        Stack<HashSet<string>> setStack = new Stack<HashSet<string>>();
        Stack<char> opStack = new Stack<char>();
        HashSet<string> currentSet = new HashSet<string>() { "" };
        int i = 0;

        while (i < expression.Length) {
            char ch = expression[i];
            if (ch == '{') {
                opStack.Push(ch);
                i++;
            } else if (ch == '}') {
                HashSet<string> unionSet = new HashSet<string>();
                while (opStack.Peek() != '{') {
                    opStack.Pop();
                    unionSet.UnionWith(currentSet);
                    currentSet = setStack.Pop();
                }
                opStack.Pop();
                currentSet.UnionWith(unionSet);
                i++;
            } else if (ch == ',') {
                setStack.Push(new HashSet<string>(currentSet));
                currentSet.Clear();
                opStack.Push(ch);
                i++;
            } else {
                int j = i;
                while (j < expression.Length && char.IsLetter(expression[j])) j++;
                string subExpr = expression.Substring(i, j - i);
                HashSet<string> newSet = new HashSet<string>();
                foreach (string prefix in currentSet) {
                    newSet.Add(prefix + subExpr);
                }
                currentSet = newSet;
                i = j;
            }
        }

        while (setStack.Count > 0) {
            currentSet.UnionWith(setStack.Pop());
        }

        List<string> result = currentSet.ToList();
        result.Sort();
        return result;
    }

    public static void Main(string[] args) {
        string expression = "{a,b}{c,{d,e}}";
        var result = new BraceExpansionII().BraceExpansionII(expression);
        Console.WriteLine(string.Join(",", result));
    }
}

This Java solution employs two stacks: one for operators (chromatically stacking characters like '{' and ','), and one for sets to manage the Union and Cartesian Product operations. The process is iterative, parsing the expression without recursion and building sets within braces.

Complexity

Time Complexity: O(n^x), where n is the complexity for nested processing and x is the nested depth.
Space Complexity: O(n^x) for storing intermediate sets due to stack operations during processing.

Try this approach in the editor

Approach 3: Default Approach

C++

class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        dfs(expression);
        return vector<string>(s.begin(), s.end());
    }

private:
    set<string> s;

    void dfs(string exp) {
        int j = exp.find_first_of('}');
        if (j == string::npos) {
            s.insert(exp);
            return;
        }
        int i = exp.rfind('{', j);
        string a = exp.substr(0, i);
        string c = exp.substr(j + 1);
        stringstream ss(exp.substr(i + 1, j - i - 1));
        string b;
        while (getline(ss, b, ',')) {
            dfs(a + b + c);
        }
    }
};

TypeScript

function braceExpansionII(expression: string): string[] {
    const dfs = (exp: string) => {
        const j = exp.indexOf('}');
        if (j === -1) {
            s.add(exp);
            return;
        }
        const i = exp.lastIndexOf('{', j);
        const a = exp.substring(0, i);
        const c = exp.substring(j + 1);
        for (const b of exp.substring(i + 1, j).split(',')) {
            dfs(a + b + c);
        }
    };
    const s: Set<string> = new Set();
    dfs(expression);
    return Array.from(s).sort();
}

func braceExpansionII(expression string) []string {
	s := map[string]struct{}{}
	var dfs func(string)
	dfs = func(exp string) {
		j := strings.Index(exp, "}")
		if j == -1 {
			s[exp] = struct{}{}
			return
		}
		i := strings.LastIndex(exp[:j], "{")
		a, c := exp[:i], exp[j+1:]
		for _, b := range strings.Split(exp[i+1:j], ",") {
			dfs(a + b + c)
		}
	}
	dfs(expression)
	ans := make([]string, 0, len(s))
	for k := range s {
		ans = append(ans, k)
	}
	sort.Strings(ans)
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Depth-First Parsing Approach	Time Complexity: O(n^k) in the worst case, where n is the length of the expression and k is the number of nested braces and operations. Space Complexity: O(n^k), due to multiple recursive calls and storage of intermediate results in sets.
Iterative Stack-Based Approach	Time Complexity: O(n^x), where n is the complexity for nested processing and x is the nested depth. Space Complexity: O(n^x) for storing intermediate sets due to stack operations during processing.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Depth-First Parsing with Backtracking	O(n * k)	O(n * k)	Best for recursive parsing of nested brace expressions
Iterative Stack-Based Evaluation	O(n * k)	O(n * k)	When avoiding recursion or implementing expression-style parsing

Frequently asked questions

Is Brace Expansion II easy or hard?

Brace Expansion II is classified as a Hard problem because it combines parsing, recursion, and set-based combination logic. Handling nested braces, union operations, and concatenation correctly requires careful expression evaluation design.

Brace Expansion II Python/Java solution

Python solutions usually implement recursive DFS parsing with sets and string concatenation. Java solutions often use iterative stack-based parsing with HashSet structures to track partial expansions. Both approaches run in roughly O(n * k) time.

How to solve Brace Expansion II in O(n)?

A strict O(n) solution is not possible because the algorithm must generate every expanded string. The best achievable complexity is proportional to the output size, typically O(n * k). Efficient implementations minimize overhead by using sets and combining partial results only when necessary.

What is the best approach for Brace Expansion II?

Depth-first parsing with backtracking is the most common approach. It treats the expression like a grammar with union and concatenation operations and recursively evaluates nested braces. Using sets ensures duplicates are removed automatically. The time complexity is roughly O(n * k), where k is the number of generated strings.

Is Brace Expansion II asked at Google/Amazon/Meta?

Brace-style parsing problems appear in interviews at companies like Google and Amazon because they test recursion, parsing, and data structure usage. Variations of expression parsing and grammar evaluation are common system and algorithm interview topics.

What data structure is used in Brace Expansion II?

Typical implementations use sets to store unique intermediate strings and either recursion or stacks to manage nested braces. Stacks help evaluate expressions iteratively, while recursion naturally handles nested parsing structures.

What is the time complexity of Brace Expansion II?

The time complexity is O(n * k), where n is the length of the expression and k is the total number of generated output strings. Each expansion step may combine sets of strings using Cartesian products. The space complexity is also O(n * k) because all generated strings must be stored.

Brace Expansion II solution and explanation

The problem

Approach overview

Approach 1: Depth-First Parsing Approach

Approach 2: Iterative Stack-Based Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Brace Expansion II solution and explanation

The problem

Approach overview

Approach 1: Depth-First Parsing Approach

Approach 2: Iterative Stack-Based Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems