1. Recursion

Intuition

The string consists of segments that are either single characters or groups of options inside braces. We process the string from left to right, extracting the options for each position. For the first position, we get all possible characters (sorted if from braces), then recursively generate all words from the remaining string. Each option at the current position is combined with each word from the recursive result.

Algorithm

  1. Define a helper function to extract options at the current position:
    • If the character is not '{', return just that character.
    • Otherwise, collect all characters until '}', sort them, and return the list.
  2. Define a recursive function to generate all words from a starting position:
    • Base case: if at the end of the string, return a list containing an empty string.
    • Get the options for the current position and the starting index of the remaining string.
    • Recursively generate all words from the remaining string.
    • Combine each option with each word from the recursive result.
  3. Call the recursive function starting at position 0 and return the result.
class Solution:
    def expand(self, s: str) -> List[str]:
        def storeFirstOptions(startPos, firstOptions):
            # If the first character is not '{', it means a single character
            if s[startPos] != '{':
                firstOptions.append(s[startPos])
            else:
                # Store all the characters between '{' and '}'
                while s[startPos] != '}':
                    if 'a' <= s[startPos] <= 'z':
                        firstOptions.append(s[startPos])
                    startPos += 1
                # Sort the list
                firstOptions.sort()
            # Increment it to point to the next character to be considered
            return startPos + 1

        def findAllWords(startPos):
            # Return empty string list if the string is empty
            if startPos == len(s):
                return [""]

            firstOptions = []
            # Store the characters for the first index as string in firstOptions
            remStringStartPos = storeFirstOptions(startPos, firstOptions)
            wordsWithRemString = findAllWords(remStringStartPos)

            expandedWords = []
            # Create new words by adding the character at the beginning
            for c in firstOptions:
                for word in wordsWithRemString:
                    expandedWords.append(c + word)

            return expandedWords

        return findAllWords(0)

Time & Space Complexity

  • Time complexity: O(N⋅3N/7)O(N \cdot 3^{N/7})

  • Space complexity: O(N⋅3N/7)O(N \cdot 3^{N/7})

Where NN is the length of the given string.

2. Iteration

Intuition

Instead of using recursion, we can build the words iteratively. Starting with an empty string, we process each segment of the input. For each segment, we take all current words and extend each one with every option from that segment. This is similar to a Cartesian product, building up the result position by position.

Algorithm

  1. Initialize expandedWords with a single empty string.
  2. Iterate through the input string:
    • Extract the options at the current position (single char or sorted chars from braces).
    • For each existing word in expandedWords and each option:
      • Create a new word by appending the option to the existing word.
    • Replace expandedWords with the newly created words.
    • Move the position to the next segment.
  3. Return expandedWords.
class Solution:
    def expand(self, s: str) -> List[str]:
        def storeFirstOptions(startPos, firstOptions):
            # If the first character is not '{', it means a single character
            if s[startPos] != '{':
                firstOptions.append(s[startPos])
            else:
                # Store all the characters between '{' and '}'
                while s[startPos] != '}':
                    if 'a' <= s[startPos] <= 'z':
                        firstOptions.append(s[startPos])
                    startPos += 1
                # Sort the list
                firstOptions.sort()
            # Increment it to point to the next character to be considered
            return startPos + 1

        expandedWords = [""]
        startPos = 0
        while startPos < len(s):
            firstOptions = []
            # Store the characters for the first index as string in firstOptions
            remStringStartPos = storeFirstOptions(startPos, firstOptions)

            currWords = []
            # Append the string in the list firstOptions to string in expandedWords
            for word in expandedWords:
                for c in firstOptions:
                    currWords.append(word + c)

            # Update the list expandedWords to have all the words
            expandedWords = currWords
            # Pointing to the next character to be considered
            startPos = remStringStartPos

        return expandedWords

Time & Space Complexity

  • Time complexity: O(N⋅3N/7)O(N \cdot 3^{N/7})

  • Space complexity: O(N⋅3N/7)O(N \cdot 3^{N/7})

Where NN is the length of the given string.

3. Backtracking

Intuition

Backtracking is a natural fit for generating all combinations. First, we parse the input string to extract all options for each position. Then we build words character by character: at each position, we try each available option, add it to the current word, recurse to the next position, and then remove it (backtrack) to try the next option.

Algorithm

  1. Parse the input string to create a list of options for each position:
    • For each segment, extract either a single character or sorted characters from braces.
  2. Define a recursive backtracking function:
    • Base case: if the current string length equals the number of positions, add it to the result.
    • Get the options for the current position.
    • For each option:
      • Append the character to the current string.
      • Recurse to fill the next position.
      • Remove the last character (backtrack).
  3. Call the backtracking function with an empty string and return the result.
class Solution:
    def expand(self, s: str) -> List[str]:
        all_options = []
        
        # Store all options for each position
        def store_all_options():
            pos = 0
            while pos < len(s):
                curr_options = []
                # If the first character is not '{', it means a single character
                if s[pos] != '{':
                    curr_options.append(s[pos])
                else:
                    # Store all the characters between '{' and '}'
                    while s[pos] != '}':
                        if 'a' <= s[pos] <= 'z':
                            curr_options.append(s[pos])
                        pos += 1
                    # Sort the list
                    curr_options.sort()
                all_options.append(curr_options)
                pos += 1
        
        def generate_words(curr_string, expanded_words):
            # If the currString is complete, we can store and return
            if len(curr_string) == len(all_options):
                expanded_words.append(''.join(curr_string))
                return
            
            # Fetch the options for the current index
            curr_options = all_options[len(curr_string)]
            
            # Add the character and go into recursion
            for c in curr_options:
                curr_string.append(c)
                generate_words(curr_string, expanded_words)
                # Backtrack to previous state
                curr_string.pop()
        
        # Store the character options for different indices
        store_all_options()
        expanded_words = []
        generate_words([], expanded_words)
        return expanded_words

Time & Space Complexity

  • Time complexity: O(N⋅3N/7)O(N \cdot 3^{N/7})

  • Space complexity: O(N)O(N)

Where NN is the length of the given string.

Common Pitfalls

Forgetting to Sort Options Within Braces

The problem requires the output to be in lexicographically sorted order. Options within braces like {b,a,c} must be sorted to [a,b,c] before generating combinations, otherwise the final result will be out of order.

# Wrong: using options in original order
options = ['b', 'a', 'c']
# Correct: sort first
options.sort()  # ['a', 'b', 'c']

Incorrect Index Advancement After Closing Brace

When parsing a brace group, after finding }, you must advance the index past the } character. Off-by-one errors here cause infinite loops or skipped characters.

# Wrong: not advancing past '}'
while s[pos] != '}':
    pos += 1
# Missing: pos += 1 after the loop

Not Handling Single Characters Outside Braces

Single characters outside braces (like a in a{b,c}) should be treated as a group with one option. Forgetting this case causes the character to be skipped entirely in the output.