// Runtime: 1 ms, faster than 100.00% of Java online submissions for Letter Case Permutation.
// Memory Usage: 38.1 MB, less than 96.00% of Java online submissions for Letter Case Permutation.

class Solution {
    public List<String> letterCasePermutation(String S) {
        char[] chars = S.toCharArray();
        List<String> result = new ArrayList<>();
        helper(chars, 0, result);
        return result;
    }

    private void helper(char[] chars, int i, List<String> result) {
        if (i == chars.length) {
            result.add(new String(chars));
            return;
        }


        char ch = chars[i];
        if (Character.isDigit(ch)) {
            helper(chars, i + 1, result);
        }
        if (Character.isLetter(ch)) {
            chars[i] = Character.toUpperCase(ch);
            helper(chars, i + 1, result);
            chars[i] = Character.toLowerCase(ch);
            helper(chars, i + 1, result);
        }
    }
}