Brace Expansion
Asked at Anduril
Problem
Brace Expansion takes a pattern like "{a,b}c{d,e}f", where each brace group lists alternative letters, and asks for every word it can produce, sorted lexicographically. There is no nesting, so parse the pattern into a list of option groups and take their Cartesian product.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
Parse first: turn the string into a list of groups, where a plain letter is a group of size 1 and {x,y,z} is a group of three options.
The result is the Cartesian product of the groups. Build it with backtracking (choose one option per group) or iteratively (extend every partial word with each option).
Sort each group before expanding. Then backtracking generates words in lexicographic order automatically — no final sort needed.
Walkthrough for "{a,b}c{d,e}f": groups [a,b] [c] [d,e] [f] -> acdf, acef, bcdf, bcef.
The output can have up to the product of group sizes entries, so complexity is dominated by output size.
Optimal Approach
Step 1: Parse into groups: on {, read letters until } (skip commas) and sort them; otherwise the single letter is a group.
Step 2: res = [""].
Step 3: For each group, res = [w + c for w in res for c in group].
Step 4: Return res (already sorted because groups are sorted and processed in order).
Time: O(L * P) where P is the number of words and L their length. Space: O(L * P).
What Trips People Up in Real Interviews
Forgetting to sort the output. Sorting each group up front is the cheap way to get it for free.
Treating commas as characters in the result.
Using recursion with string slicing on the raw pattern at every step — parse once, then expand.
Assuming nested braces. This version has none; mention that Brace Expansion II handles nesting with a grammar.
Solution Code
def expand(s):
groups = []
i = 0
while i < len(s):
if s[i] == '{':
j = s.index('}', i)
groups.append(sorted(s[i + 1:j].split(',')))
i = j + 1
else:
groups.append([s[i]])
i += 1
res = ['']
for g in groups:
res = [w + c for w in res for c in g]
return resFrequently Asked Questions
What is the Brace Expansion problem?
Brace Expansion takes a pattern like `"{a,b}c{d,e}f"`, where each brace group lists alternative letters, and asks for every word it can produce, sorted lexicographically. There is no nesting, so parse the pattern into a list of option groups and take their Cartesian product.
How do you solve Brace Expansion?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Brace Expansion?
Brace Expansion is asked at Anduril. It is a medium difficulty problem.
What are common mistakes on Brace Expansion?
- Forgetting to sort the output. Sorting each group up front is the cheap way to get it for free.
- Treating commas as characters in the result.
- Using recursion with string slicing on the raw pattern at every step — parse once, then expand.
- Assuming nested braces. This version has none; mention that Brace Expansion II handles nesting with a grammar.