Domain 2MediumMEDIUM

Letter Case Permutation

Generate all permutations of a string by changing the case of each letter using recursive backtracking.

Domain: medium•Updated: 2026-08-31
#backtracking#recursion#O(N*2^K)#O(K+N)

Problem Breakdown

We are given an alphanumeric string SS. Our goal is to generate every possible variation where each alphabetic character can independently exist in either lowercase or uppercase form, while digits remain unchanged.

Inputs: A single string SS containing letters and/or digits (length 1-12).
Outputs: A list of strings representing all valid permutations. Order does not matter.

Implicit Constraints & Edge Cases:

  • No Letters: If the input contains only digits, there is exactly one permutation (the original string itself). The logic must handle this without branching infinitely or crashing.
  • All Same Case: Input might already be all uppercase; we still need to generate both cases for every letter in our output list.
  • String Immutability: In Python, strings are immutable. We cannot modify characters in place like C++ char[]. This dictates whether we use recursion with string concatenation or a mutable character array (list) approach. Given the small constraint (N≤12N \le 12), recursive string building is clean and performant enough without needing complex buffer management.

Intuition

This problem maps directly to generating permutations based on independent choices at each position.

Brute Force: One might think of iterating through all possible strings, but that’s impossible since the search space isn’t contiguous integers. We need a constructive approach.

Key Insight: Each alphabetic character represents a binary decision (Lowercase vs Uppercase). Digits represent a single path (no choice). This structure suggests a Depth-First Search (DFS) or Backtracking tree where:

  1. If we encounter a digit, we proceed to the next index without branching.
  2. If we encounter a letter, we branch into two recursive calls: one appending the lowercase version and another appending the uppercase version of that character.

Why Brute Force is Insufficient: A naive brute force would try random swaps or generate strings randomly until all are found (O(N!)O(N!) worst case without structure). We need to systematically explore exactly 2K2^K leaves where KK is the count of letters, ensuring we don’t miss any combinations.

Approach

We will implement a recursive backtracking function dfs(index).

  1. Base Case: When index equals the length of string SS, it means we have successfully constructed one valid permutation. We append this current state to our result list and return.
  2. Recursive Step:
    • Check if character at index is a digit (isdigit()). If true, recurse with dfs(index + 1) passing the same string (or appending the char).
    • If it’s a letter: We make two recursive calls to explore both cases. One call appends the lowercase version of the current character; the second call appends the uppercase version.
  3. State Management: Since Python strings are immutable, we pass current_string + new_char in each recursion step. This is clean and readable for N≤12N \le 12.

Complexity Analysis

  • Time Complexity: O(N⋅2K)O(N \cdot 2^K) where NN is the length of string SS, and KK is the number of alphabetic characters. We generate a total of 2K2^K permutations, each requiring O(N)O(N) time to construct (due to string concatenation in Python). Given constraints (N≤12N \le 12), this effectively simplifies to roughly proportional to output size, which is acceptable for interview standards here.
  • Space Complexity: O(K+N)O(K + N). We use recursion stack depth of KK plus the space required to store the result list (which dominates). Auxiliary space excluding results and input/output storage is minimal (O(N)O(N) due to string copies in Python’s immutable nature, though technically we could optimize with a mutable buffer for strict memory constraints).

Solution

from typing import List

class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        res = []
        
        # Helper function for backtracking
        def backtrack(index, current_string):
            # Base case: if we've processed the entire string
            if index == len(S):
                res.append(current_string)
                return
            
            char = S[index]
            
            # If character is a digit, only one path (keep as is)
            if not char.isalpha():
                backtrack(index + 1, current_string + char)
            else:
                # Branch for lowercase and uppercase variations of the letter
                backtrack(index + 1, current_string + char.lower())
                backtrack(index + 1, current_string + char.upper())

        backtrack(0, "")
        
        return res

Edge Cases Handled

  • Digits Only: The isalpha() check ensures digits trigger only a single recursive call. If S="3z4"S = "3z4", ‘3’ and ‘4’ pass through unchanged; ‘z’ branches into two paths (‘Z’, ‘z’). Result count is correct (212^1).
  • Empty String: While constraints say length ≥1\ge 1, the logic holds: index == len(S) triggers immediately on entry, returning [[""] ]. (Though LeetCode guarantees non-empty input here).
  • Mixed Case Input: The code explicitly calls .lower() and .upper(), ensuring that regardless of how SS is initially cased, we generate the full set of permutations. For example, if ‘A’ comes in as uppercase, it still generates both “a” and “A”.