class Solution {
    int storeFirstOptions(String s, int startPos, List<Character> firstOptions) {
        // If the first character is not '{', it means a single character
        if (s.charAt(startPos) != '{') {
            firstOptions.add(s.charAt(startPos));
        } else {
            // Store all the characters between '{' and '}'
            while (s.charAt(startPos) != '}') {
                 if (s.charAt(startPos) >= 'a' && s.charAt(startPos) <= 'z') {
                     firstOptions.add(s.charAt(startPos));
                 }
                startPos++;
            }
            
            // Sort the list
            Collections.sort(firstOptions);
        }
        
        // Increment it to point to the next character to be considered
        return startPos + 1;
    }
    
    String[] findAllWords(String s, int startPos) {
        // Return empty string list if the string is empty
        if (startPos == s.length()) {
            return new String[] {""};
        }
        
        List<Character> firstOptions = new ArrayList<>();
        
        // Store the characters for the first index as string in firstOptions
        int remStringStartPos = storeFirstOptions(s, startPos, firstOptions);
        String[] wordsWithRemString = findAllWords(s, remStringStartPos);
        
        List<String> expandedWords = new ArrayList<>();
        
        // Create new words by adding the character at the beginning
        for (Character c : firstOptions) {
            for (String word : wordsWithRemString) {
                expandedWords.add(c + word);
            }
        }
        
        return expandedWords.toArray(new String[0]);
    }
    
    public String[] expand(String s) {
        return findAllWords(s, 0);
    }
}

class Solution {
    int storeFirstOptions(String s, int startPos, List<String> firstOptions) {
        // If the first character is not '{', it means a single character
        if (s.charAt(startPos) != '{') {
            firstOptions.add(String.valueOf(s.charAt(startPos)));
        } else {
            // Store all the characters between '{' and '}'
            while (s.charAt(startPos) != '}') {
                if (s.charAt(startPos) >= 'a' && s.charAt(startPos) <= 'z') {
                    firstOptions.add(String.valueOf(s.charAt(startPos)));
                }
                startPos++;
            }

            // Sort the list
            Collections.sort(firstOptions);
        }

        // Increment it to point to the next character to be considered
        return startPos + 1;
    }
    
    String[] expand(String s) {
        List<String> expandedWords = Arrays.asList("");
        
        int startPos = 0;
        while (startPos < s.length()) {
            List<String> firstOptions = new ArrayList<>();
            // Store the characters for the first index as string in firstOptions
            int remStringStartPos = storeFirstOptions(s, startPos, firstOptions);
            
            List<String> currWords = new ArrayList<>();
            // Append the string in the list firstOptions to string in expandedWords
            for (String word : expandedWords) {
                for (String c : firstOptions) {
                    currWords.add(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.toArray(new String[0]);
    }
}

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