Stripe Interview Question: Brace Expansion

Inspired by Bash Shell's brace expansion, this problem appears frequently in Stripe and Google interviews. It evaluates your skills in Recursion and String Parsing.

Problem Description

Implement a function that expands a string containing curly braces {} into a list of all possible combinations.

Rules

1. Comma Separated: Items inside braces are comma-separated options.
   • {a,b,c} -> ["a", "b", "c"]
2. Prefix/Suffix: Text outside braces is attached to each option.
   • pre{a,b}post -> ["preapost", "prebpost"]
3. Concatenation: Multiple brace blocks generate a Cartesian product.
   • {a,b}{1,2} -> ["a1", "a2", "b1", "b2"]

Example

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

oavoservice Solution Analysis

This can be solved using DFS (Depth-First Search) or Backtracking.

1. Recursive Strategy

Identify the first complete {...} block.

• pre: Substring before the brace.
• options: The list inside the braces.
• post: Substring after the brace.

For each opt in options, form a new string pre + opt + post. Recursively call the expand function on this new string until no braces remain.

2. Handling Multiple Braces

Example: {a,b}{1,2}

• First pass expands {a,b}: yields a{1,2} and b{1,2}.
• Second pass expands {1,2} for each: yields a1, a2 and b1, b2.

3. Stack Approach (Iterative)

You can also use a stack.

• Push static text until {.
• Upon }, pop and compute the Cartesian product with the current options.

Code Snippet (DFS Python)

def expand(s):
    if '{' not in s:
        return [s]
    
    # Find the first closing brace '}'
    r = s.find('}')
    # Find the matching opening brace '{' before it
    l = s.rfind('{', 0, r)
    
    # Split components
    prefix = s[:l]
    suffix = s[r+1:]
    options = s[l+1:r].split(',')
    
    res = []
    for opt in options:
        # Concatenate and recurse
        # Note: We resolved one pair of braces, now recurse on the result
        res.extend(expand(prefix + opt + suffix))
        
    # Sort and deduplicate if required
    return sorted(list(set(res)))

Note: This simple DFS works well for typical cases. Complex nesting might require a robust Parser implementation.

Struggling with Edge Cases?

oavoservice offers full-score support for HackerRank / CodeSignal assessments and 1-on-1 coding coaching. We teach you Pattern Recognition to tackle string parsing problems efficiently using proven templates.

Get Help