# LeetCode 1096: Brace Expansion II

## Problem Restatement

We are given a string `expression` representing a set of strings under a brace expansion language:

- A letter `c` represents the set `{c}`.
- `{e1, e2, ...}` represents the union of the sets.
- `e1 e2` (concatenation) represents all strings formed by concatenating one from each.

Return all strings in the resulting set in sorted order.

The official constraints state that `1 <= expression.length <= 60`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Expression string |
| Output | Sorted list of all strings in the generated set |

Function shape:

```python
def braceExpansionII(expression: str) -> list[str]:
    ...
```

## Examples

Example 1:

```python
expression = "{a,b}{c,{d,e}}"
```

`{a,b}` = `{a, b}`, `{c,{d,e}}` = `{c, d, e}`.

Concatenation: `{ac, ad, ae, bc, bd, be}`.

Answer:

```python
["ac", "ad", "ae", "bc", "bd", "be"]
```

## Key Insight

Use a stack-based approach. Each stack level holds a list of "current groups" being concatenated.

- `{`: Push a new level onto the stack.
- `}`: Pop the current level, union its groups, concatenate with the level below.
- `,`: Move the current group to the union list and start a new group.
- letter: Extend the current group by concatenating this letter.

## Algorithm

1. Maintain a stack where each element is a list of sets (groups separated by commas).
2. Push a new list with one empty-set group when `{` is seen.
3. On `,`: append a new empty group.
4. On `}`: compute the union of all groups on the top level, pop the level, and concatenate the union with the previous level's current group.
5. On letter: concatenate the letter to each string in the current group.

## Edge Cases

- The stack should store exactly the unresolved items needed by the invariant.
- Process equal values deliberately; many monotonic-stack problems differ only in `<` versus `<=`.
- Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * 2^n)` | Exponential in worst case |
| Space | `O(2^n)` | Output size |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def braceExpansionII(self, expression: str) -> list[str]:
        stack = [[{""}]]

        for ch in expression:
            if ch == '{':
                stack.append([{""}])
            elif ch == '}':
                groups = stack.pop()
                union = set().union(*groups)
                cur = stack[-1][-1]
                cur = {a + b for a in cur for b in union}
                stack[-1][-1] = cur
            elif ch == ',':
                stack[-1].append({""})
            else:
                cur = stack[-1][-1]
                cur = {s + ch for s in cur}
                stack[-1][-1] = cur

        return sorted(stack[0][0])
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.braceExpansionII("{a,b}{c,{d,e}}") == ["ac","ad","ae","bc","bd","be"]
    assert s.braceExpansionII("{{a,z},a{b,c},{ab,z}}") == ["a","ab","ac","z"]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| Two brace groups | `["ac","ad","ae","bc","bd","be"]` | Cross product of two sets |
| Nested braces | `["a","ab","ac","z"]` | Union removes duplicates |