Brace Expansion II

Hard
1423.

Brace Expansion II

Brace Expansion II is a hard coding problem on strings, breadth-first search and stack, asked in Amazon and Google interviews.

An expression describes a set of lowercase words. Write R(e) for the set that expression e stands for. The grammar has three rules:

  • A single lowercase letter x stands for the set with one word: R("a") = {"a"}.
  • A comma-separated list of two or more expressions inside braces stands for the union of their sets: R("{a,b,c}") = {"a","b","c"} and R("{{a,b},{b,c}}") = {"a","b","c"}.
  • Two expressions written next to each other stand for every concatenation of a word from the first with a word from the second: R("{a,b}{c,d}") = {"ac","ad","bc","bd"} and R("a{b,c}{d,e}f") has 4 words.

Given expression, return the words of R(expression) with no duplicates, in sorted (lexicographic) order.

Example 1

Input
expression = "{c,k}{o,{d,e}}"
Output
["cd","ce","co","kd","ke","ko"]

Example 2

Input
expression = "{{a,b},a{x,y},{ab,z}}"
Output
["a","ab","ax","ay","b","z"]
Explanation
Duplicates such as the second `a` disappear in the union.

Example 3

Input
expression = "k{ai,i}ro"
Output
["kairo","kiro"]

Constraints

  • 1 <= expression.length <= 60
  • expression[i] is '{', '}', ',' or a lowercase English letter
  • expression follows the grammar above
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} expression
 * @return {string[]}
 */
var braceExpansionII = function(expression) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Brace Expansion II — Solution in Python, Java & C++

Brace Expansion II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Brace Expansion II is a hard coding problem on strings, breadth-first search and stack, asked in Amazon and Google interviews.

Problem statement

An expression describes a set of lowercase words. Write R(e) for the set that expression e stands for. The grammar has three rules:

  • A single lowercase letter x stands for the set with one word: R("a") = {"a"}.
  • A comma-separated list of two or more expressions inside braces stands for the union of their sets: R("{a,b,c}") = {"a","b","c"} and R("{{a,b},{b,c}}") = {"a","b","c"}.
  • Two expressions written next to each other stand for every concatenation of a word from the first with a word from the second: R("{a,b}{c,d}") = {"ac","ad","bc","bd"} and R("a{b,c}{d,e}f") has 4 words.

Given expression, return the words of R(expression) with no duplicates, in sorted (lexicographic) order.

Example 1

Input: expression = "{c,k}{o,{d,e}}"
Output: ["cd","ce","co","kd","ke","ko"]

Example 2

Input: expression = "{{a,b},a{x,y},{ab,z}}"
Output: ["a","ab","ax","ay","b","z"]
Explanation: Duplicates such as the second `a` disappear in the union.

Example 3

Input: expression = "k{ai,i}ro"
Output: ["kairo","kiro"]

Constraints

  • 1 <= expression.length <= 60
  • expression[i] is '{', '}', ',' or a lowercase English letter
  • expression follows the grammar above

Hints for Brace Expansion II

  1. Hint 1

    There are two operators: union (,) and concatenation (adjacency). Concatenation binds tighter, like * over +.

  2. Hint 2

    Parse with two mutually recursive functions: one reads a comma-separated union, the other reads a run of adjacent items, each item being a letter or a braced union.

  3. Hint 3

    Represent each partial result as a set of strings: union merges sets, concatenation forms the cartesian product. Sort the final set.

How to solve Brace Expansion II

The grammar is an expression language with two operators — union and concatenation — so a small recursive-descent parser that evaluates each sub-expression to a set of words solves it directly.

Approach

  1. parseUnion: read one concatenation; while the next character is ,, skip it and union in another concatenation.
  2. parseConcat: start with the set {""}. While the next character is neither , nor } nor the end: if it is {, skip it, read a parseUnion, and skip the }; otherwise take the single letter. Replace the accumulated set by the cartesian product with that item.
  3. Evaluate the whole string with parseUnion, then sort the words.

Why it works

parseConcat stops exactly at the characters that end a concatenation (, belongs to the enclosing union, } to the enclosing brace), so each function consumes precisely the text of the rule it implements, mirroring the grammar's precedence. Using sets at every level removes duplicates as soon as they arise, so the result is the set R(expression).

Complexity

  • Time — O(L · W) roughly, where W is the number of words produced (bounded by the 60-character input)
  • Space — O(W · L)

Pitfalls

  • Concatenation binds tighter than the comma: {a,b}c inside braces is {a, bc}, not {ac, bc}.
  • Deduplicate — the same word can be produced by different branches.
  • Sort the output; set iteration order is arbitrary in most languages.

Reference solution

Python

from typing import List

def braceExpansionII(expression: str) -> List[str]:
    s = expression
    pos = [0]

    def parse_union():
        result = set(parse_concat())
        while pos[0] < len(s) and s[pos[0]] == ',':
            pos[0] += 1
            result |= parse_concat()
        return result

    def parse_concat():
        result = {''}
        while pos[0] < len(s) and s[pos[0]] not in ',}':
            if s[pos[0]] == '{':
                pos[0] += 1
                part = parse_union()
                pos[0] += 1
            else:
                part = {s[pos[0]]}
                pos[0] += 1
            result = {a + b for a in result for b in part}
        return result

    return sorted(parse_union())

Java

private static String braceSrc;
private static int bracePos;

private static Set<String> braceUnionPart() {
    Set<String> result = braceConcatPart();
    while (bracePos < braceSrc.length() && braceSrc.charAt(bracePos) == ',') {
        bracePos++;
        result.addAll(braceConcatPart());
    }
    return result;
}

private static Set<String> braceConcatPart() {
    Set<String> result = new HashSet<>();
    result.add("");
    while (bracePos < braceSrc.length() && braceSrc.charAt(bracePos) != ',' && braceSrc.charAt(bracePos) != '}') {
        Set<String> part;
        if (braceSrc.charAt(bracePos) == '{') {
            bracePos++;
            part = braceUnionPart();
            bracePos++;
        } else {
            part = new HashSet<>();
            part.add(String.valueOf(braceSrc.charAt(bracePos)));
            bracePos++;
        }
        Set<String> next = new HashSet<>();
        for (String a : result) for (String b : part) next.add(a + b);
        result = next;
    }
    return result;
}

public static String[] braceExpansionII(String expression) {
    braceSrc = expression;
    bracePos = 0;
    TreeSet<String> sorted = new TreeSet<>(braceUnionPart());
    return sorted.toArray(new String[0]);
}

C++

set<string> braceUnionPart(const string& s, int& pos);

set<string> braceConcatPart(const string& s, int& pos) {
    set<string> result;
    result.insert("");
    while (pos < (int)s.size() && s[pos] != ',' && s[pos] != '}') {
        set<string> part;
        if (s[pos] == '{') {
            pos++;
            part = braceUnionPart(s, pos);
            pos++;
        } else {
            part.insert(string(1, s[pos]));
            pos++;
        }
        set<string> next;
        for (const string& a : result)
            for (const string& b : part) next.insert(a + b);
        result = next;
    }
    return result;
}

set<string> braceUnionPart(const string& s, int& pos) {
    set<string> result = braceConcatPart(s, pos);
    while (pos < (int)s.size() && s[pos] == ',') {
        pos++;
        set<string> more = braceConcatPart(s, pos);
        result.insert(more.begin(), more.end());
    }
    return result;
}

vector<string> braceExpansionII(string expression) {
    int pos = 0;
    set<string> all = braceUnionPart(expression, pos);
    return vector<string>(all.begin(), all.end());
}

JavaScript

var braceExpansionII = function(expression) {
    var s = expression, pos = 0;
    var parseUnion = function() {
        var result = parseConcat();
        while (pos < s.length && s[pos] === ",") {
            pos++;
            parseConcat().forEach(function(w) { result.add(w); });
        }
        return result;
    };
    var parseConcat = function() {
        var result = new Set([""]);
        while (pos < s.length && s[pos] !== "," && s[pos] !== "}") {
            var part;
            if (s[pos] === "{") {
                pos++;
                part = parseUnion();
                pos++;
            } else {
                part = new Set([s[pos]]);
                pos++;
            }
            var next = new Set();
            result.forEach(function(a) {
                part.forEach(function(b) { next.add(a + b); });
            });
            result = next;
        }
        return result;
    };
    return Array.from(parseUnion()).sort();
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Breadth-First Search (BFS)