Brace Expansion II - Practice Coding Problems

Brace Expansion II - Problem

Hash Table String Backtracking Stack Breadth-First Search Sorting Hard

Under a specific grammar, strings can represent a set of lowercase words. Given an expression following this grammar, return the sorted list of words that the expression represents.

The grammar rules are:

Single letters: R("a") = {"a"}
Union (comma-separated): R("{a,b,c}") = {"a","b","c"}
Concatenation: R("{a,b}{c,d}") = {"ac","ad","bc","bd"}

More complex example: R("a{b,c}{d,e}f{g,h}") = {"abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"}

Note that union removes duplicates, so R("{{a,b},{b,c}}") = {"a","b","c"}

Input & Output

Example 1 — Basic Union and Concatenation

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

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

💡 Note: First group {a,b} gives {a,b}, second group {c,d} gives {c,d}. Cartesian product: a×{c,d} = {ac,ad}, b×{c,d} = {bc,bd}. Final result sorted: ["ac","ad","bc","bd"]

Example 2 — Nested Braces with Duplicates

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

› Output: ["a","b","c"]

💡 Note: Inner group {a,b} gives {a,b}, inner group {b,c} gives {b,c}. Union of both groups: {a,b} ∪ {b,c} = {a,b,c}. Duplicates removed, sorted: ["a","b","c"]

Example 3 — Complex Mixed Expression

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

› Output: ["abdf","abef","acdf","acef"]

💡 Note: Start with 'a'. Group {b,c} gives {b,c}. Concatenate: a×{b,c} = {ab,ac}. Group {d,e} gives {d,e}. Concatenate: {ab,ac}×{d,e} = {abd,abe,acd,ace}. Finally add 'f': {abdf,abef,acdf,acef}

Constraints

1 ≤ expression.length ≤ 60
expression[i] consists of '{', '}', ',', and lowercase English letters
The given expression represents a set of words based on the grammar given in the description

Visualization

Tap to expand

Understanding the Visualization

Input

Brace expression with unions and concatenations

Parse

Identify braces, commas, and characters

Expand

Generate all possible combinations

Output

Sorted unique words

Key Takeaway

🎯 Key Insight: Parse nested braces recursively, combining sets with union and concatenation operations

Asked in

G Google 45 F Facebook 32 a Amazon 28 M Microsoft 25

The key insight is to parse the nested brace structure recursively, handling union operations (comma-separated) and concatenation operations (adjacent elements). Best approach uses recursive parsing with sets for deduplication. Time: O(N × M), Space: O(M)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-based Parsing	O(N × M)	O(M + D)	Use a stack to handle nested braces and build expressions iteratively
Recursive Parsing with Set Operations	O(N × M)	O(M)	Parse the expression recursively, handling unions and concatenations with sets

Stack-based Parsing — Algorithm Steps

Initialize stack for tracking nested levels
Process each character sequentially
Push state when entering braces
Pop and combine when exiting braces
Handle unions and concatenations at each level

Visualization

Tap to expand

Step-by-Step Walkthrough

Push States

Enter new brace level

Process Characters

Build strings at current level

Pop and Combine

Merge results when exiting level

Final Result

Stack contains all combinations

Code -

solution.c — C

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

#define MAX_WORDS 10000
#define MAX_LEN 100
#define MAX_STACK 1000

typedef struct {
    char words[MAX_WORDS][MAX_LEN];
    int count;
} StringSet;

StringSet stack[MAX_STACK];
int stackTop = -1;
char finalWords[MAX_WORDS][MAX_LEN];
int finalCount = 0;

void addToSet(StringSet* set, const char* word) {
    for (int i = 0; i < set->count; i++) {
        if (strcmp(set->words[i], word) == 0) {
            return;
        }
    }
    strcpy(set->words[set->count], word);
    set->count++;
}

void pushSet(const char* word) {
    stackTop++;
    stack[stackTop].count = 0;
    addToSet(&stack[stackTop], word);
}

StringSet popSet() {
    StringSet result = stack[stackTop];
    stackTop--;
    return result;
}

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

char** solution(char* expression) {
    stackTop = -1;
    finalCount = 0;
    
    pushSet("");
    
    int i = 0;
    while (i < strlen(expression)) {
        char c = expression[i];
        
        if (c == '{') {
            pushSet("");
            i++;
        } else if (c == '}') {
            StringSet top = popSet();
            StringSet prev = popSet();
            
            stackTop++;
            stack[stackTop].count = 0;
            
            for (int p = 0; p < prev.count; p++) {
                for (int t = 0; t < top.count; t++) {
                    char combined[MAX_LEN];
                    strcpy(combined, prev.words[p]);
                    strcat(combined, top.words[t]);
                    addToSet(&stack[stackTop], combined);
                }
            }
            i++;
        } else if (c == ',') {
            StringSet top = popSet();
            
            if (stackTop >= 0) {
                for (int j = 0; j < top.count; j++) {
                    addToSet(&stack[stackTop], top.words[j]);
                }
                pushSet("");
            } else {
                stackTop++;
                stack[stackTop] = top;
                pushSet("");
            }
            i++;
        } else {
            StringSet top = popSet();
            
            stackTop++;
            stack[stackTop].count = 0;
            
            for (int j = 0; j < top.count; j++) {
                char newWord[MAX_LEN];
                strcpy(newWord, top.words[j]);
                strncat(newWord, &c, 1);
                newWord[strlen(newWord)] = '\0';
                addToSet(&stack[stackTop], newWord);
            }
            i++;
        }
    }
    
    if (stackTop >= 0) {
        for (int i = 0; i < stack[stackTop].count; i++) {
            strcpy(finalWords[finalCount], stack[stackTop].words[i]);
            finalCount++;
        }
    }
    
    qsort(finalWords, finalCount, sizeof(finalWords[0]), compare);
    return (char**)finalWords;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(N × M)

N characters processed, M words generated in worst case

✓ Linear Growth

Space Complexity

O(M + D)

M for result words, D for stack depth (nesting level)

✓ Linear Space

23.2K Views

Medium Frequency

~35 min Avg. Time

892 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

Stack-based Parsing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler