// Runtime: 1 ms, faster than 100.00% of Java online submissions for Letter Case Permutation.
// Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Letter Case Permutation.
class Solution {
    public List<String> letterCasePermutation(String S) {
        List<String> results = new ArrayList<String>();

        go(S.toCharArray(), 0, new char[S.length()], results);

        return results;
    }

    private void go(char[] input, int index, char[] output, List<String> results) {
        if (index >= input.length) {
            results.add(new String(output));
            return;
        }

        char lower = Character.toLowerCase(input[index]);
        char upper = Character.toUpperCase(input[index]);

        output[index] = lower;
        go(input, index + 1, output, results);

        if (upper != lower) {
            output[index] = upper;
            go(input, index + 1, output, results);
        }
    }
}