LeetCode 784 - Letter Case Permutation

Difficulty: 🟡 Medium
Topics: String, Backtracking, Bit Manipulation

Solution

Problem Understanding

The problem asks us to generate every possible string that can be formed by independently changing the case of each alphabetic character in the input string.

Digits cannot be modified, so they always remain the same in every generated result. Only English letters can change between lowercase and uppercase.

For example, if the input is "a1b2", there are two letters, 'a' and 'b'. Each letter has two possible states:

lowercase
uppercase

That means the total number of combinations is:

$2^2 = 4$

The four valid outputs are:

"a1b2"
"a1B2"
"A1b2"
"A1B2"

The input length is at most 12, which is relatively small. Even if every character is a letter, the maximum number of permutations is:

$2^{12} = 4096$

This is small enough that generating all combinations explicitly is completely feasible.

An important observation is that every letter represents a binary choice:

use lowercase
use uppercase

This naturally suggests a backtracking or recursive exploration approach.

Several edge cases are important:

Strings containing only digits, such as "123", should return exactly one result because there are no letters to modify.
Strings containing only letters generate the maximum number of combinations.
Mixed uppercase and lowercase input should still work correctly because each letter can always be converted to both lowercase and uppercase.
A single-character string such as "a" or "1" should still return a valid list.

The problem guarantees that the string contains only English letters and digits, so we do not need to handle special symbols or Unicode characters.

Approaches

Brute Force Approach

A brute force strategy would try every possible combination of uppercase and lowercase assignments for all positions in the string, regardless of whether the character is a digit or a letter.

One way to think about this is:

Suppose the string has length n
There are potentially 2^n binary combinations
For every combination, decide whether each position should be uppercase or lowercase

However, this wastes work because digits do not actually have two valid states. The brute force method would still iterate through all bitmask combinations and repeatedly process characters that never change.

The approach is correct because it systematically explores every possible assignment of character cases. Eventually, every valid permutation appears exactly once.

The downside is unnecessary processing and less clean logic.

Optimal Approach, Backtracking

The better approach is to use backtracking and only branch when the current character is a letter.

The key insight is that:

Digits contribute exactly one choice
Letters contribute exactly two choices

So instead of exploring useless branches, we recursively build strings character by character:

If the current character is a digit, append it and continue.
If the current character is a letter:
recurse with lowercase
recurse with uppercase

This avoids redundant work and directly models the structure of the problem.

Backtracking is a natural fit because we are generating all possible combinations under a sequence of choices.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × 2^n)	O(n × 2^n)	Explores all bitmasks regardless of whether characters are digits
Optimal	O(n × 2^L)	O(n × 2^L)	Only branches on letters, where L is the number of letters

Algorithm Walkthrough

Step 1: Create a Result List

We maintain a list called result that stores all generated permutations.

Each completed permutation will eventually be added to this list.

Step 2: Define a Backtracking Function

The recursive function needs two pieces of information:

the current index in the string
the partially constructed string

The recursive state represents:

"All valid permutations that can be formed from this position onward."

Step 3: Handle the Base Case

If the index reaches the length of the string, we have processed every character.

At this point:

the current path forms a complete valid permutation
append it to the result list

Then return to continue exploring other branches.

Step 4: Process Digits

If the current character is a digit:

append it unchanged
recurse to the next index

Digits create only one branch because their value cannot change.

Step 5: Process Letters

If the current character is alphabetic:

recurse once using lowercase
recurse once using uppercase

This creates the branching structure that generates every valid permutation.

Step 6: Continue Until All Branches Finish

The recursion tree eventually explores every possible letter-case combination.

Once recursion completes, the result list contains all valid strings.

Why it works

The algorithm works because every letter contributes exactly two independent choices, lowercase or uppercase. The recursion systematically explores both possibilities for every letter while preserving fixed digits unchanged.

At each recursive level:

one character position is finalized
all valid possibilities for remaining positions are explored

Since every valid choice is explored exactly once, the algorithm generates every valid permutation without duplicates or omissions.

Python Solution

from typing import List

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        result = []

        def backtrack(index: int, current: str) -> None:
            if index == len(s):
                result.append(current)
                return

            char = s[index]

            if char.isdigit():
                backtrack(index + 1, current + char)
            else:
                backtrack(index + 1, current + char.lower())
                backtrack(index + 1, current + char.upper())

        backtrack(0, "")
        return result

The implementation begins by creating an empty result list that stores all generated permutations.

The nested backtrack function performs the recursive exploration. It accepts:

index, the current position in the input string
current, the partially constructed permutation

The base case occurs when index == len(s). This means every character has been processed, so the constructed string is complete and added to the result list.

For each recursive step:

If the character is a digit, recursion continues with only one branch because digits do not change.
If the character is a letter, recursion branches into two paths:
lowercase version
uppercase version

The recursion tree naturally generates all valid combinations.

Finally, the algorithm starts recursion from index 0 with an empty string.

Go Solution

func letterCasePermutation(s string) []string {
	var result []string

	var backtrack func(index int, current string)

	backtrack = func(index int, current string) {
		if index == len(s) {
			result = append(result, current)
			return
		}

		char := s[index]

		if char >= '0' && char <= '9' {
			backtrack(index+1, current+string(char))
		} else {
			lower := string(char | 32)
			upper := string(char &^ 32)

			backtrack(index+1, current+lower)
			backtrack(index+1, current+upper)
		}
	}

	backtrack(0, "")
	return result
}

The Go solution follows the same recursive structure as the Python version.

One notable difference is how character case conversion is handled. Instead of calling built-in string methods repeatedly, the implementation uses ASCII bit manipulation:

char | 32 converts a letter to lowercase
char &^ 32 converts a letter to uppercase

This works because English letters follow predictable ASCII bit patterns.

Go strings are immutable, just like Python strings, so concatenation creates new strings during recursion.

The result slice starts as nil, which is perfectly valid in Go and behaves correctly with append.

Worked Examples

Example 1

Input:

s = "a1b2"

There are two letters:

Total permutations:

$2^2 = 4$

Recursive Exploration

Step	Index	Current String	Action
1	0	`""`	Process `'a'`
2	1	`"a"`	Digit `'1'`, continue
3	2	`"a1"`	Process `'b'`
4	3	`"a1b"`	Digit `'2'`, continue
5	4	`"a1b2"`	Add to result
6	3	`"a1B"`	Digit `'2'`, continue
7	4	`"a1B2"`	Add to result
8	1	`"A"`	Digit `'1'`, continue
9	2	`"A1"`	Process `'b'`
10	3	`"A1b"`	Digit `'2'`, continue
11	4	`"A1b2"`	Add to result
12	3	`"A1B"`	Digit `'2'`, continue
13	4	`"A1B2"`	Add to result

Final result:

["a1b2", "a1B2", "A1b2", "A1B2"]

Example 2

Input:

s = "3z4"

Only one letter exists:

Total permutations:

$2^1 = 2$

Recursive Exploration

Step	Index	Current String	Action
1	0	`""`	Digit `'3'`
2	1	`"3"`	Process `'z'`
3	2	`"3z"`	Digit `'4'`
4	3	`"3z4"`	Add to result
5	2	`"3Z"`	Digit `'4'`
6	3	`"3Z4"`	Add to result

Final result:

["3z4", "3Z4"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × 2^L)	There are `2^L` permutations, each requiring up to `n` characters to build
Space	O(n × 2^L)	Output storage dominates, recursion depth is at most `n`

Here, L represents the number of alphabetic characters in the string.

Each letter doubles the number of generated permutations. Since every generated string has length n, constructing and storing results requires proportional work and memory.

The recursion stack itself only requires O(n) space, but the output list dominates total memory usage.

Test Cases

solution = Solution()

# Example 1
assert sorted(solution.letterCasePermutation("a1b2")) == sorted([
    "a1b2",
    "a1B2",
    "A1b2",
    "A1B2"
])

# Example 2
assert sorted(solution.letterCasePermutation("3z4")) == sorted([
    "3z4",
    "3Z4"
])

# Single lowercase letter
assert sorted(solution.letterCasePermutation("a")) == sorted([
    "a",
    "A"
])

# Single uppercase letter
assert sorted(solution.letterCasePermutation("Z")) == sorted([
    "z",
    "Z"
])

# Only digits
assert sorted(solution.letterCasePermutation("123")) == sorted([
    "123"
])

# Mixed uppercase and lowercase
assert sorted(solution.letterCasePermutation("aB")) == sorted([
    "ab",
    "aB",
    "Ab",
    "AB"
])

# Maximum branching with all letters
result = solution.letterCasePermutation("abcd")
assert len(result) == 16  # 2^4 permutations

# Digits between letters
assert sorted(solution.letterCasePermutation("1a2")) == sorted([
    "1a2",
    "1A2"
])

# Alternating letters and digits
result = solution.letterCasePermutation("x1y2")
assert sorted(result) == sorted([
    "x1y2",
    "x1Y2",
    "X1y2",
    "X1Y2"
])

# Length 1 digit
assert solution.letterCasePermutation("7") == ["7"]

Test	Why
`"a1b2"`	Standard mixed input example
`"3z4"`	Single letter case branching
`"a"`	Smallest alphabetic input
`"Z"`	Uppercase input handling
`"123"`	No branching at all
`"aB"`	Mixed initial casing
`"abcd"`	Exponential branching behavior
`"1a2"`	Digits surrounding a letter
`"x1y2"`	Multiple separated letters
`"7"`	Single digit boundary case

Edge Cases

Input Contains Only Digits

A string like "12345" can easily expose bugs in implementations that assume every character creates two branches.

In this case, the correct answer contains exactly one string because digits never change. The implementation handles this correctly by creating only one recursive branch whenever isdigit() returns true.

Input Contains Only Letters

A string like "abcd" creates the maximum number of permutations for its length.

This is important because the recursion tree doubles at every character. The implementation correctly explores both lowercase and uppercase branches for every position, generating all 2^n possibilities.

Input Already Contains Uppercase Letters

An input such as "aB" is important because some incorrect solutions only convert lowercase letters to uppercase and ignore existing uppercase letters.

The implementation avoids this issue by always generating:

char.lower()
char.upper()

This guarantees correctness regardless of the original casing of the input.

Single Character Input

Inputs like "a" or "7" are minimal boundary cases.

These cases verify that:

recursion terminates correctly
the base case appends completed strings properly
no extra permutations are generated

The implementation handles these naturally because the recursion stops exactly when the index reaches the string length.