# Letter Case Permutation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/letter-case-permutation)
Canonical: https://scaleengineer.com/dsa/problems/letter-case-permutation
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** String
**Companies:** [Yelp](https://scaleengineer.com/companies/yelp)
---
## Problem
Given a string `s`, you can transform every letter individually to be lowercase or uppercase to create another string.

Return _a list of all possible strings we could create_. Return the output in **any order**.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `1 <= s.length <= 12`
* `s` consists of lowercase English letters, uppercase English letters, and digits.

# Approaches
## Iterative Approach (BFS)
This approach iteratively builds the list of all possible permutations. It starts with a list containing just an empty string. Then, for each character in the input string, it expands the list of permutations. If the character is a letter, it doubles the size of the list by creating two new versions for each existing permutation (one with the lowercase letter, one with the uppercase). If it's a digit, it simply appends the digit to every existing permutation.
**Time:** O(N * 2^L), where N is the length of the string and L is the number of letters. For each of the `N` characters, we iterate through the current list of permutations and create new strings. The total number of generated strings is proportional to `N * 2^L`. · **Space:** O(N * 2^L), where N is the length of the string and L is the number of letters. This is dominated by the space required to store the `2^L` output strings of length `N`. The intermediate list `newPermutations` also contributes to this.
**Pros:** It's an iterative approach, so it avoids recursion and the risk of stack overflow.; The logic is straightforward and easy to follow.
**Cons:** Creating a new list (`newPermutations`) in each iteration can lead to significant memory allocation and garbage collection overhead.; String concatenation in a loop (`p + c`) creates many intermediate string objects, which is inefficient.
### Explanation
This method can be visualized as a Breadth-First Search (BFS) through the decision tree of possibilities. We maintain a list of all permutations generated so far. We process the input string character by character, and at each step `i`, we use the permutations of length `i` to generate all permutations of length `i+1`.

For example, with `s = "a1b"`:
1. Start with `permutations = [""]`.
2. Process 'a': `permutations` becomes `["a", "A"]`.
3. Process '1': `permutations` becomes `["a1", "A1"]`.
4. Process 'b': `permutations` becomes `["a1b", "a1B", "A1b", "A1B"]`.

While conceptually simple, this implementation creates a new list and new strings at each step, which can be inefficient.

```java
class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> permutations = new ArrayList<>();
        if (s == null) {
            return permutations;
        }
        permutations.add("");

        for (char c : s.toCharArray()) {
            List<String> newPermutations = new ArrayList<>();
            for (String p : permutations) {
                if (Character.isLetter(c)) {
                    newPermutations.add(p + Character.toLowerCase(c));
                    newPermutations.add(p + Character.toUpperCase(c));
                } else {
                    newPermutations.add(p + c);
                }
            }
            permutations = newPermutations;
        }
        return permutations;
    }
}
```
### Algorithm
- Initialize a list of strings, `permutations`, and add an empty string to it.
- Iterate through each character `c` of the input string `s`.
- For each character, create a temporary list `newPermutations`.
- Iterate through each string `p` currently in the `permutations` list.
- If `c` is a letter, add two new strings to `newPermutations`: `p` with the lowercase of `c` appended, and `p` with the uppercase of `c` appended.
- If `c` is a digit, add one new string to `newPermutations`: `p` with `c` appended.
- After processing all strings for the current character, replace `permutations` with `newPermutations`.
- After iterating through all characters of `s`, the `permutations` list holds the final result.

## Backtracking (Recursive DFS)
This approach uses recursion with backtracking, which is a natural fit for permutation and combination problems. We traverse the string, and at each character, we make a decision. If the character is a letter, we explore two branches: one for its lowercase form and one for its uppercase form. If it's a digit, we only explore one path. This effectively performs a Depth-First Search (DFS) on the decision tree.
**Time:** O(N * 2^L). The recursion tree has `2^L` leaf nodes. At each leaf, we do O(N) work to create a new string. The total number of nodes in the tree is about `2 * 2^L`, and the work at each node is constant, leading to the overall complexity. · **Space:** O(N * 2^L). The output list requires this much space. The auxiliary space used by the recursion stack is O(N).
**Pros:** The code is elegant and directly models the problem's recursive structure.; The in-place modification of a character array is very efficient in terms of auxiliary space (O(N) for the recursion stack).
**Cons:** Involves recursion, which adds function call overhead.; For extremely long strings (not the case here due to constraints), it could lead to a stack overflow error.
### Explanation
The core idea is to build the permutations in place using a character array. A recursive function explores all possibilities by changing characters at the current position and then calling itself for the next position. After a recursive call returns (i.e., after exploring a branch), the state is implicitly restored because the subsequent recursive call will overwrite the character at the same position.

This in-place modification is more memory-efficient than creating new strings at each step of the recursion.

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

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

        char c = chars[index];
        if (Character.isLetter(c)) {
            // Lowercase branch
            chars[index] = Character.toLowerCase(c);
            backtrack(chars, index + 1, result);

            // Uppercase branch
            chars[index] = Character.toUpperCase(c);
            backtrack(chars, index + 1, result);
        } else {
            // Digit branch
            backtrack(chars, index + 1, result);
        }
    }
}
```
### Algorithm
- Convert the input string `s` to a character array `chars` for efficient in-place modification.
- Create a result list `result`.
- Define a recursive helper function, `backtrack(index)`.
- **Base Case:** If `index` equals the length of `chars`, it means a full permutation has been formed. Convert the `chars` array to a string and add it to `result`. Then, return.
- **Recursive Step:**
  - Get the character `c` at `chars[index]`.
  - If `c` is a letter:
    - Set `chars[index]` to its lowercase version and make a recursive call: `backtrack(index + 1)`.
    - Set `chars[index]` to its uppercase version and make another recursive call: `backtrack(index + 1)`.
  - If `c` is a digit:
    - Make a single recursive call: `backtrack(index + 1)`.
- Start the process by calling `backtrack(0)`.

## Bit Manipulation
This clever approach maps each permutation to a unique integer. If there are `L` letters in the string, there are `2^L` possible case combinations. We can iterate through numbers from `0` to `2^L - 1`. Each number's binary representation (as a bitmask of length `L`) dictates the case for each letter in a specific permutation. For example, the `k`-th bit of the number can decide the case of the `k`-th letter in the string.
**Time:** O(N * 2^L). We have an outer loop that runs `2^L` times, and an inner loop that runs `N` times to build each string. · **Space:** O(N * 2^L). This is dominated by the storage for the result list. Auxiliary space is O(N) for the `StringBuilder`.
**Pros:** Highly efficient iterative solution that avoids recursion overhead.; Uses fast bitwise operations.; The total number of permutations is known before the main loop begins.
**Cons:** The logic can be less intuitive to grasp compared to a direct backtracking approach.; It typically requires a pre-computation step to count the letters or find their indices.
### Explanation
We can directly generate each of the `2^L` permutations without recursion. We loop `2^L` times. In each iteration `i`, we construct the `i`-th permutation. The binary representation of `i` serves as a blueprint. For instance, if `i` is `5` (binary `101`), it could mean the 1st letter is uppercase, 2nd is lowercase, and 3rd is uppercase. We iterate through the input string, and when we encounter a letter, we use the next available bit from our counter `i` to decide its case.

```java
class Solution {
    public List<String> letterCasePermutation(String s) {
        int letterCount = 0;
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                letterCount++;
            }
        }

        int numPermutations = 1 << letterCount;
        List<String> result = new ArrayList<>(numPermutations);

        for (int i = 0; i < numPermutations; i++) {
            StringBuilder sb = new StringBuilder();
            int letterIndex = 0;
            for (char c : s.toCharArray()) {
                if (Character.isLetter(c)) {
                    // Check the bit for the current letter
                    if (((i >> letterIndex) & 1) == 1) {
                        sb.append(Character.toUpperCase(c));
                    } else {
                        sb.append(Character.toLowerCase(c));
                    }
                    letterIndex++;
                } else {
                    sb.append(c);
                }
            }
            result.add(sb.toString());
        }
        return result;
    }
}
```
### Algorithm
- First, count the number of letters, `L`, in the input string `s`.
- The total number of permutations is `total = 2^L`.
- Initialize an empty list `result` to store the final strings.
- Loop with a counter `i` from `0` to `total - 1`.
- For each `i`, we will generate one unique permutation.
  - Create a `StringBuilder`.
  - Initialize a `letter_bit_pos` counter to `0`.
  - Iterate through the input string `s` character by character.
  - If the character `c` is a letter:
    - Check the `letter_bit_pos`-th bit of `i` using `(i >> letter_bit_pos) & 1`.
    - If the bit is `1`, append the uppercase version of `c`.
    - If the bit is `0`, append the lowercase version of `c`.
    - Increment `letter_bit_pos`.
  - If the character is a digit, append it as is.
  - After building the string, add it to the `result` list.
- Return the `result` list.

# Solutions
### Java

```java
class Solution { private List < String > ans = new ArrayList <>(); private char [] t ; public List < String > letterCasePermutation ( String s ) { t = s . toCharArray (); dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i >= t . length ) { ans . add ( String . valueOf ( t )); return ; } dfs ( i + 1 ); if ( t [ i ] >= 'A' ) { t [ i ] ^= 32 ; dfs ( i + 1 ); } } }
```

### CPP

```cpp
class Solution { public: vector < string > letterCasePermutation ( string s ) { vector < string > ans ; function < void ( int ) > dfs = [ & ]( int i ) { if ( i >= s . size ()) { ans . emplace_back ( s ); return ; } dfs ( i + 1 ); if ( s [ i ] >= 'A' ) { s [ i ] ^= 32 ; dfs ( i + 1 ); } }; dfs ( 0 ); return ans ; } };
```

### Python

```python
class Solution : def letterCasePermutation ( self , s : str ) -> List [ str ]: def dfs ( i ): if i >= len ( s ): ans . append ( '' . join ( t )) return dfs ( i + 1 ) if t [ i ]. isalpha (): t [ i ] = chr ( ord ( t [ i ]) ^ 32 ) dfs ( i + 1 ) t = list ( s ) ans = [] dfs ( 0 ) return ans
```