Letter Case Permutation

Given a string s, transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Example 1

Input: s = "a1b2" → Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2

Input: s = "3z4" → Output: ["3z4","3Z4"]

Solution Approach

Use backtracking: iterate through each character. If it is a digit, skip it. If it is a letter, branch into two recursive calls: one with lowercase and one with uppercase.

Start DFS at index 0 with the original string as a char array.
At each index, if it is a digit move to index+1.
If it is a letter, convert to lowercase, recurse, then convert to uppercase and recurse again.
When index == s.length(), add the current char array (as string) to results.

Java

import java.util.*;

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

    private void backtrack(char[] cs, int i, List<String> res) {
        if (i == cs.length) {
            res.add(new String(cs));
            return;
        }
        backtrack(cs, i + 1, res);
        if (Character.isLetter(cs[i])) {
            cs[i] ^= 32; // toggle case
            backtrack(cs, i + 1, res);
            cs[i] ^= 32; // restore
        }
    }
}

Time Complexity: O(2^L * N) where L is number of letters
Space Complexity: O(N * 2^L) for result storage