Backtracking - 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.

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

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

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.

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