/*
Runtime: 2 ms, faster than 83.45% of Java online submissions for Letter Case Permutation.
Memory Usage: 37.9 MB, less than 100.00% of Java online submissions for Letter Case Permutation.
*/

class Solution {
    List<String> result;
    public List<String> letterCasePermutation(String S) {
        result = new ArrayList<String>();
        go(S.toCharArray(), 0);
        return result;
    }

    void go(char[] s, int idx) {
        if (idx >= s.length) {
            result.add(new String(s));
            return;
        }

        int nextId = idx + 1;
        // while (nextId < s.length && !Character.isLetter(s[nextId])) nextId++;
        if (Character.isLetter(s[idx])) {
            s[idx] = flip(s[idx]);
            go(s, nextId);
            s[idx] = flip(s[idx]);
        }
        go (s, nextId);
    }

    char flip(char c) {
        if (Character.isUpperCase(c)) return Character.toLowerCase(c);
        return Character.toUpperCase(c);
     }
}