Letter Case Permutation: Branching on Every Letter

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 you could create. You may return the output in any order.

This is LeetCode 784: Letter Case Permutation. For input "a1b2", the output is ["a1b2", "a1B2", "A1b2", "A1B2"]. Digits stay fixed. Only letters contribute to branching.

Why this problem matters

Letter Case Permutation sits at the intersection of three patterns: string manipulation, backtracking, and bit manipulation. It is a gentler entry point than Subsets because the branching logic is simpler. At each position, you either have two choices (lowercase or uppercase, if it is a letter) or one choice (keep it, if it is a digit). There is no pruning, no constraints to check, and no duplicate handling.

This makes it an excellent problem for building intuition about decision trees. Every problem that asks "generate all variations" maps onto a tree where each node represents a choice. Once you see that structure here, you will recognize it in Permutations, Combinations, and Subsets.

The bit manipulation approach adds a second dimension. If there are k letters in the string, there are 2^k permutations, one for each binary number from 0 to 2^k - 1. Each bit controls whether a specific letter is lowercase or uppercase. This connection between enumeration and binary counting shows up in many combinatorial problems.

The approach

There are two clean ways to solve this.

Backtracking (recursive)

Walk through the string one character at a time. At each position:

1. If the character is a digit, keep it and move to the next position.
2. If the character is a letter, branch: recurse once with lowercase, once with uppercase.
3. When you reach the end of the string, record the result.

This is the standard choose-explore-unchoose pattern, except there is no explicit "unchoose" step because you build a new string at each level rather than modifying a shared path in place.

Bit manipulation (iterative)

Count the number of letters in s. Call it k. There are 2^k permutations. For each number mask from 0 to 2^k - 1, build a string: scan through s, and for each letter, check the next bit of mask. If the bit is 0, use lowercase. If 1, use uppercase. Digits stay unchanged.

Clean solution

Backtracking

def letterCasePermutation(s: str) -> list[str]:
    result = []

    def backtrack(i, built):
        if i == len(s):
            result.append(built)
            return

        if s[i].isalpha():
            backtrack(i + 1, built + s[i].lower())
            backtrack(i + 1, built + s[i].upper())
        else:
            backtrack(i + 1, built + s[i])

    backtrack(0, "")
    return result

Bit manipulation

def letterCasePermutation(s: str) -> list[str]:
    letters = [i for i, c in enumerate(s) if c.isalpha()]
    k = len(letters)
    result = []

    for mask in range(1 << k):
        chars = list(s)
        for j, idx in enumerate(letters):
            if mask & (1 << j):
                chars[idx] = chars[idx].upper()
            else:
                chars[idx] = chars[idx].lower()
        result.append("".join(chars))

    return result

Step-by-step walkthrough

The backtracking naturally produces a depth-first traversal of the decision tree. At each letter, the recursion forks into two paths. At each digit, it continues in a straight line. The total number of results equals 2^k, where k is the number of letters in the input.

Notice that the digit positions never cause branching. The character '1' at index 1 and '2' at index 3 simply pass through unchanged. Only the letters 'a' and 'b' create forks, giving us 2^2 = 4 results.

Complexity analysis

Here n is the length of the string and k is the number of letter characters.

Time is O(n * 2^k) for both approaches. There are 2^k permutations, and building each one takes O(n) time (either through string concatenation during recursion or through list construction during bit iteration).

Space is O(n * 2^k) to store all results. The backtracking approach also uses O(n) recursion stack depth. The bit manipulation approach uses O(n) for the character array. In both cases, the output dominates.

The building blocks

This problem is built on two core reusable pieces.

Binary decision backtracking

At each position, you make a binary choice (lowercase or uppercase) or no choice (digit). This is the simplest form of backtracking because there are no constraints to check and no pruning to apply.

def backtrack(i, built):
    if i == len(s):
        result.append(built)
        return

    if s[i].isalpha():
        backtrack(i + 1, built + s[i].lower())
        backtrack(i + 1, built + s[i].upper())
    else:
        backtrack(i + 1, built + s[i])

This same "binary choice at each position" pattern appears in Subsets, where you decide to include or exclude each element. The skeleton is nearly identical.

Bitmask enumeration

When you have k independent binary choices, iterate from 0 to 2^k - 1 and use each bit to make a decision. This technique converts any binary decision tree into a flat loop.

The bitmask approach is especially useful when the number of choices is small (like 26 letters or fewer) and you want to avoid recursion overhead. You will see this same pattern in problems like Subsets (iterative solution) and anywhere you need to enumerate all subsets of a small set.

Edge cases to watch for

• All digits: "123" has zero letters, so k = 0 and there is exactly one permutation: "123".
• All letters: "abc" has three letters, producing 2^3 = 8 permutations.
• Single character: "a" produces ["a", "A"]. "1" produces ["1"].
• Mixed case input: "a1B2" should still produce all case variations. Treat each letter independently regardless of its original case.
• Empty string: The constraints guarantee s.length is at least 1, but if you handle it, the answer is [""].

From understanding to recall

You understand the decision tree. You see how letters fork and digits pass through. But can you write both the backtracking and bit manipulation solutions from memory in under three minutes?

That is the gap between understanding and interview readiness. The backtracking version is short, but under pressure, you might fumble the base case or forget to handle digits separately. The bitmask version requires remembering to pre-collect letter indices and map bits to positions correctly.

Spaced repetition bridges this gap. You practice writing the binary decision backtracking pattern and the bitmask enumeration pattern at increasing intervals until they become automatic. When you see "generate all variations" in an interview, the code flows out without hesitation.

Related posts

• Subsets - Same branching decision tree pattern
• Permutations - Classic backtracking with similar recursive structure
• Combinations - Another backtracking problem that builds results incrementally