Marc Lester Tan

class Solution {
    public String[] expand(String S) {
        List<String> collector = new ArrayList<>();
        
        helper(0, S, "", collector);
        Collections.sort(collector);
        
        return collector.toArray(new String[0]);
    }
    
    private void helper(int index, String input, String current, List<String> collector) {
        if(index == input.length()){
            collector.add(current);
            return;
        }
        
        char inputChar = input.charAt(index);
        
        if(inputChar == '{') {
            // start collecting chars
            index++;
            List<Character> cList = new ArrayList<>();
            while(index < input.length() && input.charAt(index) != '}'){
                if(Character.isLetter(input.charAt(index))){
                    cList.add(input.charAt(index));    
                }
                index++;                
            }
            
            index++;
            
            // then recursively call helper function
            // by appending each character to the current string
            for(Character c : cList){
                helper(index, input, current + c, collector);
            }
        }else {
            // if the current character isn't a start of braces and it's just 
            // a letter, just append it to the current string.
            helper(index + 1, input, current + inputChar, collector);
        }
    }
}