Brace Expansion - Practice Coding Problems

Brace Expansion - Problem

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.

Input & Output

Example 1 — Basic Expansion

$ Input: s = "a{b,c}"

› Output: ["ab","ac"]

💡 Note: The first character is 'a', the second can be 'b' or 'c', giving us "ab" and "ac". Results are sorted lexicographically.

Example 2 — Multiple Options

$ Input: s = "{a,b}{c,d}"

› Output: ["ac","ad","bc","bd"]

💡 Note: First position has options {a,b}, second has {c,d}. All combinations: ac, ad, bc, bd. Already in lexicographical order.

Example 3 — Mixed Fixed and Variable

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

› Output: ["abde","abdf","acde","acdf"]

💡 Note: Fixed 'a', options {b,c}, fixed 'd', options {e,f}. Generate all 4 combinations and sort.

Constraints

1 ≤ s.length ≤ 50
s consists of lowercase English letters, '{', '}', and ','
All the values in s are unique

Visualization

Tap to expand

Understanding the Visualization

Input

String with braces indicating character options

Parse

Identify fixed characters and option groups

Expand

Generate all combinations systematically

Sort

Return results in lexicographical order

Key Takeaway

🎯 Key Insight: Parse options first, then systematically expand combinations level by level

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to parse the string to identify fixed characters and option groups, then systematically generate all combinations. The best approach uses iterative expansion or queue-based BFS to avoid recursion overhead. Time: O(k × n × log k), Space: O(k × n) where k is the number of combinations.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Recursion	O(k × n × log(k))	O(k × n)	Parse options and recursively generate all combinations
Backtracking with Stack	O(k × n × log(k))	O(k × n)	Use explicit stack to generate combinations iteratively
Queue-Based BFS	O(k × n × log(k))	O(k × n)	Use queue to expand combinations level by level

Brute Force with Recursion — Algorithm Steps

Parse the string to extract character options
Use recursion to build all combinations
Sort the result lexicographically

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse

Extract character options from input

Generate

Recursively build all combinations

Sort

Sort results lexicographically

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char result[1000][100];
int resultCount = 0;

void generate(char options[][10][10], int optionCounts[], int totalOptions, int index, char* current) {
    if (index == totalOptions) {
        strcpy(result[resultCount++], current);
        return;
    }
    for (int i = 0; i < optionCounts[index]; i++) {
        char next[100];
        strcpy(next, current);
        strcat(next, options[index][i]);
        generate(options, optionCounts, totalOptions, index + 1, next);
    }
}

int compare(const void* a, const void* b) {
    return strcmp((char*)a, (char*)b);
}

void solution(char* s) {
    char options[50][10][10];
    int optionCounts[50] = {0};
    int totalOptions = 0;
    int i = 0;
    
    while (i < strlen(s)) {
        if (s[i] == '{') {
            int j = i + 1;
            while (j < strlen(s) && s[j] != '}') j++;
            char optionStr[100];
            strncpy(optionStr, s + i + 1, j - i - 1);
            optionStr[j - i - 1] = '\0';
            
            char* token = strtok(optionStr, ",");
            while (token != NULL) {
                strcpy(options[totalOptions][optionCounts[totalOptions]], token);
                optionCounts[totalOptions]++;
                token = strtok(NULL, ",");
            }
            totalOptions++;
            i = j + 1;
        } else {
            options[totalOptions][0][0] = s[i];
            options[totalOptions][0][1] = '\0';
            optionCounts[totalOptions] = 1;
            totalOptions++;
            i++;
        }
    }
    
    char current[100] = "";
    generate(options, optionCounts, totalOptions, 0, current);
    qsort(result, resultCount, sizeof(result[0]), compare);
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    solution(s);
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("\"%s\"", result[i]);
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n × log(k))

k combinations generated, each of length n, plus sorting k results

⚡ Linearithmic

Space Complexity

O(k × n)

Store k result strings, each of length n, plus recursion stack

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler