LeetCode Solutions Blog

Letter Case Permutation

Number: 800

Difficulty: Medium

Paid? No

Problem Description

Given a string s, transform every letter individually to either lowercase or uppercase to form all possible strings. The output is a list of all such transformations in any order.

Key Insights

Use backtracking (or DFS) to explore all decision paths for each letter.
Only letters can change case; digits remain unchanged.
The maximum length of s is small (up to 12), making recursion feasible.

Space and Time Complexity

Time Complexity: O(2^L * L) where L is the number of letters in the string; each recursive branch processes the string. Space Complexity: O(L) for the recursion stack and O(2^L * L) for storing all permutations.

Solution

The solution uses backtracking to generate all possible strings. For each character:

If it's a digit, simply append it.
If it's a letter, recursively explore two branches: one with the letter in lowercase and another in uppercase. The approach uses a helper function that tracks the current index and the accumulated transformation. Data structures include a list (or vector/array) to store results, and the algorithm is recursive backtracking.

Code Solutions

# Define the function letterCasePermutation which takes input string s.
def letterCasePermutation(s: str) -> list:
    # List to store all possible permutations.
    result = []
    
    # Helper function for backtracking.
    def backtrack(index: int, path: list):
        # Base case: if the current index is equal to the length of s,
        # join the path list into a string and add it to result.
        if index == len(s):
            result.append("".join(path))
            return
        
        current_char = s[index]
        # If current character is a digit, simply add it and continue recursion.
        if current_char.isdigit():
            path.append(current_char)
            backtrack(index + 1, path)
            path.pop()  # backtrack by removing the last character
        else:
            # Explore the lowercase branch.
            path.append(current_char.lower())
            backtrack(index + 1, path)
            path.pop()  # backtrack
            # Explore the uppercase branch.
            path.append(current_char.upper())
            backtrack(index + 1, path)
            path.pop()  # backtrack
    
    # Start the backtracking from index 0 with an empty path.
    backtrack(0, [])
    return result

# Example usage:
# print(letterCasePermutation("a1b2"))