1096. Brace Expansion II

class Solution {
    public List<String> braceExpansionII(String expression) {
        Set<String> res = new HashSet<>();
        Deque<String> q = new ArrayDeque<>();
        q.offer(expression);
        
        while (!q.isEmpty()) {
            String cur = q.poll();
            if (cur.indexOf("{") == -1) {
                res.add(cur);
                continue;
            }
            
            int left = cur.indexOf("{");
            int index = left;
            while (index < cur.length() && cur.charAt(index) != '}') {
                if (cur.charAt(index) == '{') {
                    left = index;
                }
                index++;
            }
            int right = index;
            
            // left = { 0, right = 4 }
            // a, b
            String processed = cur.substring(0, left);
            String[] processing = cur.substring(left + 1, right).split(",");
            String unprocessed = cur.substring(right + 1);
            
            for (String part : processing) {
                StringBuilder sb = new StringBuilder(processed);
                sb.append(part).append(unprocessed);
                q.offer(sb.toString());
            }
        }
        
        List<String> resList = new ArrayList<>(res);
        Collections.sort(resList);
        return resList;
    }
}