Letter Case Permutation

This question is asked by Amazon. Given a string s consisting of only letters and digits, where we are allowed to transform any letter to uppercase or lowercase, return a list containing all possible permutations of the string.

Example(s)

Example 1:

Input: s = "c7w2"
Output: ["c7w2", "c7W2", "C7w2", "C7W2"]
Explanation:
The string has 2 letters: 'c' and 'w'
Each letter can be uppercase or lowercase
Total permutations: 2^2 = 4
  - "c7w2" (both lowercase)
  - "c7W2" (c lowercase, w uppercase)
  - "C7w2" (c uppercase, w lowercase)
  - "C7W2" (both uppercase)

Example 2:

Input: s = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
Explanation:
The string has 2 letters: 'a' and 'b'
Each letter can be uppercase or lowercase
Total permutations: 2^2 = 4

Example 3:

Input: s = "3z4"
Output: ["3z4", "3Z4"]
Explanation:
The string has 1 letter: 'z'
It can be uppercase or lowercase
Total permutations: 2^1 = 2

Example 4:

Input: s = "12345"
Output: ["12345"]
Explanation:
No letters, only digits
Only one permutation (no changes possible)

Solution

The solution uses Backtracking (DFS):

Process characters: Go through string character by character
Two choices for letters: Uppercase or lowercase
Digits unchanged: Keep digits as they are
Recursive building: Build permutations character by character

JavaScript Solution
Python Solution

JavaScript Solution - Backtracking

/**
* Generate all letter case permutations
* @param {string} s - Input string
* @return {string[]} - All possible permutations
*/
function letterCasePermutation(s) {
const result = [];
const current = [];

/**
 * Check if character is a letter
 */
function isLetter(char) {
  return (char >= 'a' && char <= 'z') || (char >= 'A' && char <= 'Z');
}

/**
 * Backtracking function
 * @param {number} index - Current character index
 */
function backtrack(index) {
  // Base case: processed all characters
  if (index === s.length) {
    result.push(current.join(''));
    return;
  }
  
  const char = s[index];
  
  // If character is a digit, add it as is
  if (!isLetter(char)) {
    current.push(char);
    backtrack(index + 1);
    current.pop();
  } else {
    // Character is a letter, try both cases
    // Option 1: Lowercase
    current.push(char.toLowerCase());
    backtrack(index + 1);
    current.pop();
    
    // Option 2: Uppercase
    current.push(char.toUpperCase());
    backtrack(index + 1);
    current.pop();
  }
}

backtrack(0);
return result;
}

// Test cases
console.log('Example 1:', letterCasePermutation("c7w2")); 
// ["c7w2", "c7W2", "C7w2", "C7W2"]

console.log('Example 2:', letterCasePermutation("a1b2")); 
// ["a1b2", "a1B2", "A1b2", "A1B2"]

console.log('Example 3:', letterCasePermutation("3z4")); 
// ["3z4", "3Z4"]

console.log('Example 4:', letterCasePermutation("12345")); 
// ["12345"]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - Backtracking

from typing import List

def letter_case_permutation(s: str) -> List[str]:
  """
  Generate all letter case permutations
  
  Args:
      s: Input string
      
  Returns:
      List[str]: All possible permutations
  """
  result = []
  current = []
  
  def is_letter(char: str) -> bool:
      """Check if character is a letter"""
      return char.isalpha()
  
  def backtrack(index: int):
      """
      Backtracking function
      
      Args:
          index: Current character index
      """
      # Base case: processed all characters
      if index == len(s):
          result.append(''.join(current))
          return
      
      char = s[index]
      
      # If character is a digit, add it as is
      if not is_letter(char):
          current.append(char)
          backtrack(index + 1)
          current.pop()
      else:
          # Character is a letter, try both cases
          # Option 1: Lowercase
          current.append(char.lower())
          backtrack(index + 1)
          current.pop()
          
          # Option 2: Uppercase
          current.append(char.upper())
          backtrack(index + 1)
          current.pop()
  
  backtrack(0)
  return result

# Test cases
print('Example 1:', letter_case_permutation("c7w2"))  
# ['c7w2', 'c7W2', 'C7w2', 'C7W2']

print('Example 2:', letter_case_permutation("a1b2"))  
# ['a1b2', 'a1B2', 'A1b2', 'A1B2']

print('Example 3:', letter_case_permutation("3z4"))  
# ['3z4', '3Z4']

print('Example 4:', letter_case_permutation("12345"))  
# ['12345']

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Iterative)

Here's an iterative solution that builds permutations level by level:

JavaScript Iterative
Python Iterative

/**
 * Iterative solution: Build permutations level by level
 */
function letterCasePermutationIterative(s) {
  let result = [''];
  
  for (const char of s) {
    const newResult = [];
    
    for (const str of result) {
      if (char >= '0' && char <= '9') {
        // Digit: add as is
        newResult.push(str + char);
      } else {
        // Letter: add both cases
        newResult.push(str + char.toLowerCase());
        newResult.push(str + char.toUpperCase());
      }
    }
    
    result = newResult;
  }
  
  return result;
}

def letter_case_permutation_iterative(s: str) -> List[str]:
    """
    Iterative solution: Build permutations level by level
    """
    result = ['']
    
    for char in s:
        new_result = []
        
        for str_val in result:
            if char.isdigit():
                # Digit: add as is
                new_result.append(str_val + char)
            else:
                # Letter: add both cases
                new_result.append(str_val + char.lower())
                new_result.append(str_val + char.upper())
        
        result = new_result
    
    return result

Complexity

Time Complexity: O(2^L × N) - Where L is the number of letters and N is the length of the string. We generate 2^L permutations, and each permutation takes O(N) to build.
Space Complexity: O(2^L × N) - For storing all permutations (excluding recursion stack).

Approach

The solution uses Backtracking (DFS):

Process characters:
- Go through string character by character from left to right
For each character:
- If digit: Add it as is (only one choice)
- If letter: Try both uppercase and lowercase (two choices)
Recursive building:
- Add character (in chosen case) to current permutation
- Recursively process next character
- Backtrack by removing the character
Base case:
- When index === s.length, we've processed all characters
- Add current permutation to results

Key Insights

Backtracking: Explore all case combinations for letters
Two choices per letter: Uppercase or lowercase
Digits unchanged: Keep digits as they are
O(2^L) permutations: Where L is number of letters
Systematic exploration: Backtracking ensures all combinations

Step-by-Step Example

Let's trace through Example 1: s = "c7w2"

s = "c7w2"
result = []
current = []

backtrack(0):
  index = 0, char = 'c' (letter)
  
  Option 1: Lowercase 'c'
    current = ['c']
    backtrack(1):
      index = 1, char = '7' (digit)
      current = ['c', '7']
      backtrack(2):
        index = 2, char = 'w' (letter)
        
        Option 1: Lowercase 'w'
          current = ['c', '7', 'w']
          backtrack(3):
            index = 3, char = '2' (digit)
            current = ['c', '7', 'w', '2']
            backtrack(4):
              index = 4 === length → add "c7w2" to result
            current.pop() → ['c', '7', 'w']
          current.pop() → ['c', '7']
        
        Option 2: Uppercase 'W'
          current = ['c', '7', 'W']
          backtrack(3):
            index = 3, char = '2' (digit)
            current = ['c', '7', 'W', '2']
            backtrack(4):
              index = 4 === length → add "c7W2" to result
            current.pop() → ['c', '7', 'W']
          current.pop() → ['c', '7']
      current.pop() → ['c']
    current.pop() → []
  
  Option 2: Uppercase 'C'
    current = ['C']
    backtrack(1):
      ... (similar, generates "C7w2", "C7W2")
    current.pop() → []

Result: ["c7w2", "c7W2", "C7w2", "C7W2"]

Visual Representation

Example 1: s = "c7w2"

Backtracking tree:
  backtrack(0)
    ├─ 'c' (lowercase) → backtrack(1)
    │   └─ '7' (digit) → backtrack(2)
    │       ├─ 'w' (lowercase) → backtrack(3)
    │       │   └─ '2' (digit) → "c7w2" ✓
    │       └─ 'W' (uppercase) → backtrack(3)
    │           └─ '2' (digit) → "c7W2" ✓
    └─ 'C' (uppercase) → backtrack(1)
        └─ '7' (digit) → backtrack(2)
            ├─ 'w' (lowercase) → backtrack(3)
            │   └─ '2' (digit) → "C7w2" ✓
            └─ 'W' (uppercase) → backtrack(3)
                └─ '2' (digit) → "C7W2" ✓

Result: ["c7w2", "c7W2", "C7w2", "C7W2"]

Total permutations: 2^2 = 4 (2 letters, each with 2 choices)

Edge Cases

Empty string: Return [""] (one empty permutation)
No letters: Return [s] (only one permutation)
All letters: Generate 2^N permutations
Mixed case input: Convert to both cases regardless of original case
Single letter: Return 2 permutations

Important Notes

Case conversion: Convert letters to both uppercase and lowercase
Digits unchanged: Keep digits exactly as they are
Original case ignored: Input case doesn't matter, we generate both
O(2^L) permutations: Where L is number of letters
Backtracking: Systematically explores all case combinations

Why Backtracking Works

Key insight:

We need to generate all possible case combinations for letters
Each letter has 2 choices (uppercase or lowercase)
This creates 2^L total permutations where L is the number of letters
Backtracking systematically explores all possibilities

Optimal substructure:

To generate permutations for s[index...], we:
- Choose a case for s[index] (if it's a letter)
- Recursively generate permutations for s[index+1...]
This creates the recursive structure

Letter Combinations of Phone Number: Similar backtracking problem
Generate Parentheses: Different backtracking problem
Subsets: Different combination problem
Permutations: Different permutation problem

Takeaways

Backtracking explores all case combinations
Two choices per letter (uppercase or lowercase)
Digits unchanged (keep as is)
O(2^L) time exponential but necessary
Classic backtracking problem with practical applications

Example(s)​

Solution​

JavaScript Solution - Backtracking

Output:

Python Solution - Backtracking

Output:

Alternative Solution (Iterative)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why Backtracking Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Iterative)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why Backtracking Works

Related Problems

Takeaways