Letter Case Permutation

LeetCode 800 | Difficulty: Medium

Medium

Problem Description

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 we could create. Return the output in any order.

Example 1:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

Input: s = "3z4"
Output: ["3z4","3Z4"]

Constraints:

- `1 <= s.length <= 12`

- `s` consists of lowercase English letters, uppercase English letters, and digits.

Topics: String, Backtracking, Bit Manipulation

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 364 ms)

Metric	Value
Runtime	364 ms
Memory	N/A
Date	2018-08-19

Solution

public class Solution {
    public IList<string> LetterCasePermutation(string S) {
        return LetterCasePermutation(S,0);
}

IList<string> LetterCasePermutation(string S, int index)
{
    List<string> result = new List<string>();
    if(index==S.Length)
    {
        return new List<string>() { string.Empty};
    }
    else
    {
        
        IList<string> perms = LetterCasePermutation(S, index + 1);
        bool isDigit = char.IsDigit(S[index]);
        foreach (var permutation in perms)
        {
            if (isDigit)
            {
                result.Add(S[index] + permutation);
            }
            else
            {
                result.Add(S[index] + permutation);
                if(char.IsLower(S[index]))
                {
                    result.Add(S[index].ToString().ToUpper() + permutation);
                }
                else
                {
                    result.Add(S[index].ToString().ToLower() + permutation);
                }
            }
        }
        return result;
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Backtracking	$O(n! or 2^n)$	$O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Identify pruning conditions early to avoid exploring invalid branches.