Is Brace Expansion easy or hard?

Brace Expansion is generally rated medium difficulty. The parsing step is straightforward, but recognizing that the problem reduces to combination generation using backtracking or BFS is the key insight.

Brace Expansion Python/Java solution

Python and Java implementations typically parse the expression into groups and use backtracking to generate results. Python solutions often use recursion with list accumulation, while Java versions use a StringBuilder for efficient string construction.

How to solve Brace Expansion in O(n)?

A strict O(n) solution is not possible because the output itself may contain many strings. The optimal approach runs in O(R * L), proportional to the total size of the generated output. Backtracking or BFS both achieve this optimal bound.

What is the best approach for Brace Expansion?

Backtracking is the most common solution. Parse the expression into segments and recursively build strings by choosing one character from each group. This directly generates every valid combination while keeping results in lexicographic order if each group is sorted.

Is Brace Expansion asked at Google/Amazon/Meta?

Brace-style expansion problems appear in interviews at large tech companies because they test recursion, parsing, and combinatorial generation. Variants of this problem have appeared in interviews at companies like Google and Amazon.

What data structure is used in Brace Expansion?

The main structures are arrays or lists to store characters in each brace group, plus either a recursion stack (backtracking) or a queue for BFS. Strings or character buffers are used to build the final combinations.

What is the time complexity of Brace Expansion?

The time complexity is O(R * L), where R is the number of generated strings and L is the length of each string. Every character of every resulting string must be constructed at least once, which dominates the runtime.

Description Hints 2 Solution Video 9:55

1087. Brace Expansion

Medium66.5% acceptance6 companiesPremium elsewhere, free here

You are given a string s representing a list of words. Each letter in the word has one or more options.

If there is one option, the letter is represented as is.
If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, if s = "a{b,c}", the first character is always 'a', but the second character can be 'b' or 'c'. The original list is ["ab", "ac"].

Return all words that can be formed in this manner, sorted in lexicographical order.

Example 1:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: s = "abcd"
Output: ["abcd"]

Constraints:

1 <= s.length <= 50
s consists of curly brackets '{}', commas ',', and lowercase English letters.
s is guaranteed to be a valid input.
There are no nested curly brackets.
All characters inside a pair of consecutive opening and ending curly brackets are different.

Asked at 6 companies

Stripe Niantic Anduril Apple

Google DoorDash

Topics

Hints open one at a time

Hint 1

All generated strings are of the same size. How can we generate all of these strings?

Hint 2

Do a backtracking on which each level of it has to choose one single (e.g. 'a') character or any character of the given parenthesized group (e.g. "{a,b,c}")

9:55

Still stuck?Read the written solution, or watch a walkthrough.

Open solution