Problem Description

Given a string s consisting of letters and digits, you are asked to return a list of all possible strings we can obtain by transforming every letter individually to be either lowercase or uppercase. Digits must remain unchanged. The order of returned permutations does not matter.

• Each letter in s can be changed independently to lowercase or uppercase.
• Digits in s are not altered.
• The output should include all possible case permutations of the input string.
• There are no duplicate permutations in the output.

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

Thought Process

At first glance, the problem seems to require generating all combinations of upper and lower case for each letter in the string, while leaving digits unchanged. A brute-force approach would try every possible combination by toggling each letter between its two cases, leading to 2^{number of letters} total permutations.

The main challenge is to systematically generate all these combinations without missing any or introducing duplicates, and to do so efficiently. Rather than generating all possible strings and filtering out duplicates, we can use recursion or iteration to build each permutation step by step, making a choice at each character.

Optimization comes from recognizing that only letters have two choices (lowercase or uppercase), while digits have a single choice (remain as is). Therefore, our approach should efficiently branch only when necessary.

Solution Approach

To solve this problem, we can use either backtracking (recursion) or iterative methods (like BFS with a queue). The core idea is to process the string character by character, and for each letter, branch into two possibilities: one with the letter in lowercase, and one in uppercase. For digits, we simply continue without branching.

• Step 1: Start with an empty permutation and at the first character of the string.
• Step 2: For each character:
  • If it's a digit, append it as is to the current permutation and move to the next character.
  • If it's a letter, recursively (or iteratively) branch into two paths: one with the lowercase version, and one with the uppercase version, then proceed to the next character in both branches.
• Step 3: When the end of the string is reached, add the current permutation to the result list.
• Data Structure: We use a list to collect all permutations. In the iterative approach, a queue or list can be used to store intermediate permutations.
• Why Backtracking? Backtracking is natural here because at each letter, we have two choices, and we want to explore all combinations. Each recursive call handles one character and all its possible continuations.

This approach ensures that all permutations are generated, and no duplicates are created since each path represents a unique combination of letter cases.

Example Walkthrough

Let's walk through the example s = "a1b2":

• Start with an empty string: ""
• First character: 'a' (letter)
  • Branch 1: "a"
  • Branch 2: "A"
• Next character: '1' (digit)
  • Both branches append '1': "a1", "A1"
• Next character: 'b' (letter)
  • Branch from "a1": "a1b", "a1B"
  • Branch from "A1": "A1b", "A1B"
• Next character: '2' (digit)
  • All branches append '2': "a1b2", "a1B2", "A1b2", "A1B2"
• All permutations are collected at this point.

Final output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Time and Space Complexity

• Brute-force approach: If we tried every possible string of the same length and filtered out those that don't match the pattern, this would be extremely inefficient and unnecessary.
• Optimized approach (backtracking):
  • Let L be the number of letters in the string. Each letter has 2 possibilities (lowercase or uppercase), so there are 2^L permutations.
  • Time Complexity: O(2^L * N), where N is the length of the string. For each of the 2^L permutations, we build a string of length N.
  • Space Complexity: O(2^L * N) for storing all permutations, plus recursion stack space of O(N) if using recursion.

Summary

The Letter Case Permutation problem asks us to generate all possible strings by toggling the case of each letter in the input, while leaving digits unchanged. By using backtracking or an iterative approach, we efficiently explore all valid permutations, branching only when letters are encountered. The total number of permutations grows exponentially with the number of letters, but the algorithm is both simple and elegant, leveraging the natural structure of the problem to avoid unnecessary work.

Code Implementation

class Solution:
    def letterCasePermutation(self, s: str):
        res = []
        def backtrack(path, idx):
            if idx == len(s):
                res.append(path)
                return
            if s[idx].isdigit():
                backtrack(path + s[idx], idx + 1)
            else:
                backtrack(path + s[idx].lower(), idx + 1)
                backtrack(path + s[idx].upper(), idx + 1)
        backtrack("", 0)
        return res
      

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        vector<string> res;
        backtrack(s, 0, res);
        return res;
    }
    void backtrack(string s, int idx, vector<string>& res) {
        if (idx == s.size()) {
            res.push_back(s);
            return;
        }
        if (isdigit(s[idx])) {
            backtrack(s, idx + 1, res);
        } else {
            s[idx] = tolower(s[idx]);
            backtrack(s, idx + 1, res);
            s[idx] = toupper(s[idx]);
            backtrack(s, idx + 1, res);
        }
    }
};
      

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> res = new ArrayList<>();
        backtrack(s.toCharArray(), 0, res);
        return res;
    }
    private void backtrack(char[] arr, int idx, List<String> res) {
        if (idx == arr.length) {
            res.add(new String(arr));
            return;
        }
        if (Character.isDigit(arr[idx])) {
            backtrack(arr, idx + 1, res);
        } else {
            arr[idx] = Character.toLowerCase(arr[idx]);
            backtrack(arr, idx + 1, res);
            arr[idx] = Character.toUpperCase(arr[idx]);
            backtrack(arr, idx + 1, res);
        }
    }
}
      

var letterCasePermutation = function(s) {
    let res = [];
    function backtrack(path, idx) {
        if (idx === s.length) {
            res.push(path);
            return;
        }
        if (/[0-9]/.test(s[idx])) {
            backtrack(path + s[idx], idx + 1);
        } else {
            backtrack(path + s[idx].toLowerCase(), idx + 1);
            backtrack(path + s[idx].toUpperCase(), idx + 1);
        }
    }
    backtrack("", 0);
    return res;
};