Problem statement
Expand a string such as {a,b}c{d,e}f. A brace group supplies alternatives for one output position; a literal supplies one fixed letter. Return every possible word in lexicographic order.
The supplied task guarantees valid input of length 1–50, lowercase single-letter options, distinct alternatives inside each group and no nested braces. Do not use this parser for {a,{b,c}} or full-word alternatives: those require a different grammar. LeetCode’s Brace Expansion is the corresponding practice destination and may require Premium; this blog’s explanation and code remain readable without it.
Constraints & requirements
- CONTRACT
- Original task: length 1–50, lowercase letters, distinct alternatives within each group, and no nested braces. This is Brace Expansion I, not the nested-expression version II. LeetCode may require Premium.
Examples 3 test cases
Example 1 Case 1
- Input
s="{a,b}c{d,e}f"- Output
[acdf,acef,bcdf,bcef]
Two independent groups with two choices each produce four words.
Example 2 Case 2
- Input
s="abcd"- Output
[abcd]
A literal character is a group with one option.
Example 3 Case 3
- Input
s="{b,a}z"- Output
[az,bz]
Sort the choices in each group before traversal.
Hints Optional
01Hint 1
Separate parsing from generation.
02Hint 2
Turn a literal into a one-choice group and each brace into a sorted choice group.
03Hint 3
At depth index, pick one letter from groups[index]; never skip a group.
How to think before coding
Separate parsing from generation. After parsing, define groups[i] as the legal letters for output position i. The recursive index counts GROUPS consumed, not raw input characters. Choose exactly one letter from that group and advance once; index==groups.size() completes a word. Sort each group before traversal for lexicographic results. No branch is allowed to skip a group.
Brute force and the improvement
A literal brute-force method tries every lowercase word of the required output length G, then checks whether each letter belongs to its position’s allowed group. That takes O(G·26^G) checking work with O(G) candidate space, excluding returned words. It wastes nearly all choices. Parse the allowed choices first and generate their Cartesian product instead: if group sizes multiply to P, only P complete words are needed. A reusable character buffer can further avoid copying intermediate prefixes; the code below keeps the original immutable-prefix version and its honest copy costs.
Intuition: separate syntax from choices
First convert the expression into [[a,b],[c],[d,e],[f]]. Now the recursion no longer needs to understand braces or commas. It only picks one letter from each list.
This is a Cartesian product, like choosing one shirt and one pair of shoes. If the groups offer 2, 1, 2 and 1 choices, there are 2×1×2×1 = 4 words.
Each recursive level represents one group, not one raw input character. Skipping a group would create a short word that the expression never described.
Algorithm
- Scan the valid expression from left to right.
- A literal becomes a one-letter group.
- For
{...}, collect its letters while ignoring commas, then sort them. - At recursive depth index, append one option from groups[index].
- Save the prefix when every group has been consumed.
Sorting each group and exploring them in sequence guarantees lexicographic output because all generated words have the same number of positions.
Java solution
The parser produces sorted choice groups. The recursive index then consumes one group per level; braces and commas never enter the output.
import java.util.*;
class Solution {
public static List<String> expand(String input) {
List<List<Character>> groups = new ArrayList<>(); // One choice list per output position.
for (int i = 0; i < input.length();) { // Valid, non-nested, single-letter-option grammar.
List<Character> group = new ArrayList<>();
if (input.charAt(i) == '{') {
i++; // Pass the opening brace.
while (input.charAt(i) != '}') {
char ch = input.charAt(i++);
if (ch != ',') group.add(ch); // Commas separate alternatives; they are not letters.
}
i++; // Pass the closing brace.
Collections.sort(group); // Sorted siblings yield sorted complete words.
} else group.add(input.charAt(i++)); // A literal has exactly one option.
groups.add(group);
}
List<String> result = new ArrayList<>();
expandGroups(groups, 0, "", result);
return result;
}
private static void expandGroups(List<List<Character>> groups, int index,
String prefix, List<String> result) {
if (index == groups.size()) { // Picked one character from EVERY group.
result.add(prefix);
return;
}
for (char choice : groups.get(index)) { // No skipping: this position must supply a character.
expandGroups(groups, index + 1, prefix + choice, result); // New String needs no explicit undo.
}
}
public static void main(String[] args) {
System.out.println(expand("{a,b}c{d,e}f")); // [acdf, acef, bcdf, bcef]
}
}The default invocation returns [acdf, acef, bcdf, bcef]. prefix + choice creates a new String, so returning from a child automatically leaves its parent’s prefix unchanged.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: input = "{a,b}c{d,e}f"
What to track: Parsed groups are [a,b], [c], [d,e], [f]. index selects a group; prefix contains one chosen letter from every earlier group.
-
Parse choices, not punctuation
Java operationif (ch != ',') group.add(ch);Stategroups = [[a,b],[c],[d,e],[f]]; index = 0; prefix = ""Braces delimit a choice group and commas separate options. Neither appears in output strings.
-
Follow the first choice at each position
Java operationexpandGroups(groups, index + 1, prefix + choice, result);State(1,"a") → (2,"ac") → (3,"acd") → (4,"acdf")There is no skip branch: every group must supply exactly one character.
-
Save the completed word
Java operationresult.add(prefix);Stateindex = groups.size() = 4; result = ["acdf"]All positions are filled. The immutable prefix can be stored directly.
-
Resume the d/e choice
Java operationfor (char choice : groups.get(index))Statewaiting frame index = 2 still has prefix = "ac"; choose e, then f; save "acef"The earlier d branch does not modify this parent prefix, so no explicit undo is needed.
-
Resume the root’s b choice
Java operationexpandGroups(groups, index + 1, prefix + choice, result);Stateroot prefix = ""; b → bc → bcd → bcdf, then bce → bcefThe complete a subtree returns before the b subtree starts. Sorted group choices produce the four sorted words.
Final result: ["acdf","acef","bcdf","bcef"]
"" ├─ a → ac │ ├─ acd → acdf → save │ └─ ace → acef → save └─ b → bc ├─ bcd → bcdf → save └─ bce → bcef → save
The c and f groups have one option but still need a recursive level. After acdf returns, the waiting ac call chooses e. It does not carry the d from the finished child, because its local String remains ac.
Why it works
Parsing preserves exactly the allowed letters at each output position. Recursion selects one allowed letter per group, so every returned word is valid. Conversely, each valid word describes one choice from every group, and traversal visits that sequence once. Sorted choices guarantee that words with a smaller first differing letter are returned first.
Complexity and alternative approaches
Let L be expression length, G the number of output positions and P the product of group sizes. Parsing is O(L), plus sorting each group. The bounded lowercase alphabet keeps individual groups small.
With immutable prefix concatenation, a safe generation bound is O(G²·P); at most O(G·P) prefix nodes each copy up to G characters. Output alone uses O(G·P). Live prefixes can occupy O(G²) auxiliary characters along the stack; group storage uses O(L).
A shared char buffer or StringBuilder can avoid intermediate copies and generate in O(G·P) work plus parsing. Iteratively extending a list of prefixes is another valid product construction, but keeps a larger frontier. Nested Brace Expansion II needs recursive parsing of union and concatenation, not just this flat scanner.
Common mistakes
- Treating commas or braces as literal output characters.
- Failing to advance past
}after collecting a group. - Assuming brace options already arrive sorted.
- Calling this a string-permutation algorithm: group positions cannot be reordered.
- Claiming malformed or nested expressions are supported by a parser written for guaranteed-valid flat input.