Brace Expansion

Brace Expansion

What is this problem about?

Brace Expansion is a string manipulation problem where you are given a string like "{a,b}c{d,e}f". You need to generate all possible strings that can be formed by choosing one character from each set of braces. The output should be sorted lexicographically. This is essentially a problem of finding the Cartesian product of several sets of characters.

Why is this asked in interviews?

Companies like Google and Stripe use this to evaluate your skills in Backtracking and string parsing. It tests how you handle recursive branching and how you maintain sorted order across generated combinations. It's a practical problem that mirrors how shell expansions work in operating systems.

Algorithmic pattern used

The primary pattern is Backtracking or DFS. First, you parse the string into a list of groups (e.g., ["a", "b"], "c", ["d", "e"], "f"). Then, you use recursion to explore every possible combination, picking one character from each group and moving to the next. Sorting each group before starting the backtracking ensures the final results are generated in lexicographical order.

Example explanation

Input: "{a,b}c{d,e}f"

1. Groups: Group 1: {a, b}, Group 2: {c}, Group 3: {d, e}, Group 4: {f}.
2. Step 1: Pick 'a' from Group 1.
3. Step 2: Pick 'c' from Group 2.
4. Step 3: Pick 'd' from Group 3.
5. Step 4: Pick 'f' from Group 4. Result: "acdf".
6. Backtrack and pick 'e' from Group 3. Result: "acef".
7. Repeat for 'b' from Group 1. Results: "bcdf", "bcef".

Common mistakes candidates make

A common mistake is forgetting to sort the results (or the groups) to meet the lexicographical requirement. Another is using inefficient string concatenation in a loop, which can lead to $O(N^2)$ behavior. Some candidates also struggle with the initial parsing of the string, especially identifying which parts are inside braces and which are not.

Interview preparation tip

When a problem asks for "all possible combinations" or "expansions," backtracking is almost always the answer. Practice parsing strings using a simple state machine or index pointer to separate the dynamic parts (braces) from the static parts.