LeetCode 784: Letter Case Permutation

Problem Restatement

We are given a string s.

Each alphabet letter may be changed independently to lowercase or uppercase.

Digits must stay the same.

Return all possible strings we can create.

The output may be returned in any order.

Input and Output

Function shape:

class Solution:
    def letterCasePermutation(self, s: str) -> list[str]:
        ...

Examples

Example 1:

s = "a1b2"

The letter a can be a or A.

The digit 1 stays the same.

The letter b can be b or B.

The digit 2 stays the same.

So the result is:

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

Example 2:

s = "3z4"

Only z can change case.

The result is:

["3z4", "3Z4"]

Example 3:

s = "12345"

There are no letters.

The only possible result is:

["12345"]

First Thought: Build Choices Character by Character

At every character, we decide what can go into the output string.

If the character is a digit, there is only one choice.

If the character is a letter, there are two choices:

This forms a decision tree.

For example, for "a1b2":

a / A
then 1
then b / B
then 2

The leaves of this decision tree are the final strings.

Key Insight

This is a backtracking problem.

We process the string from left to right.

At index i:

1. If s[i] is a digit, append it and move to i + 1.
2. If s[i] is a letter, try lowercase and uppercase.

When we reach the end of the string, we add the built string to the answer.

Algorithm

Use DFS.

1. Convert s to a list of characters so we can modify it easily.
2. Define dfs(index).
3. If index == len(s), add the current string to the answer.
4. If the current character is a digit, recurse to the next index.
5. Otherwise:
   1. Set it to lowercase and recurse.
   2. Set it to uppercase and recurse.
6. Return the answer list.

Correctness

We prove that the algorithm returns exactly all valid case permutations.

For each index, the algorithm handles the character according to the rules.

If the character is a digit, the algorithm keeps it unchanged. This is necessary because digits cannot be transformed.

If the character is a letter, the algorithm explores both valid choices: lowercase and uppercase. These are the only two allowed choices for a letter.

The recursion processes every index from left to right. When it reaches the end, one valid choice has been made for every character, so the current string is a valid permutation.

Every valid permutation corresponds to exactly one sequence of choices in the recursion: for each letter, choose its final case; for each digit, keep it fixed. Therefore, the algorithm generates every valid permutation and does not generate any invalid string.

Complexity

Let m be the number of letters in s, and let n = len(s).

The recursion stack uses O(n) extra space.

Implementation

class Solution:
    def letterCasePermutation(self, s: str) -> list[str]:
        chars = list(s)
        answer = []

        def dfs(index: int) -> None:
            if index == len(chars):
                answer.append("".join(chars))
                return

            if chars[index].isdigit():
                dfs(index + 1)
                return

            chars[index] = chars[index].lower()
            dfs(index + 1)

            chars[index] = chars[index].upper()
            dfs(index + 1)

        dfs(0)
        return answer

Code Explanation

We convert the string into a list:

chars = list(s)

Python strings are immutable, so a character list makes it easy to change one position during DFS.

The answer stores all final strings:

answer = []

When index reaches the end, the current character list is complete:

if index == len(chars):
    answer.append("".join(chars))
    return

If the current character is a digit, there is no branching:

if chars[index].isdigit():
    dfs(index + 1)
    return

For a letter, we try lowercase first:

chars[index] = chars[index].lower()
dfs(index + 1)

Then uppercase:

chars[index] = chars[index].upper()
dfs(index + 1)

The recursive calls explore all combinations of choices.

Testing

def run_tests():
    s = Solution()

    assert sorted(s.letterCasePermutation("a1b2")) == sorted([
        "a1b2",
        "a1B2",
        "A1b2",
        "A1B2",
    ])

    assert sorted(s.letterCasePermutation("3z4")) == sorted([
        "3z4",
        "3Z4",
    ])

    assert s.letterCasePermutation("12345") == ["12345"]

    assert sorted(s.letterCasePermutation("a")) == sorted([
        "a",
        "A",
    ])

    assert sorted(s.letterCasePermutation("Z")) == sorted([
        "z",
        "Z",
    ])

    print("all tests passed")

run_tests()

Test coverage: