784. Letter Case Permutation

MediumView on LeetCode

String Backtracking Bit Manipulation

Time: O(2^n)

Space: O(2^n)

Problem Overview

Each letter can be lower or upper case; digits stay fixed.

Intuition

Each letter can be lower or upper case; digits stay fixed. Backtracking explores both branches for every letter position. At the end of the string, append the built combination to the answer list.

Algorithm

1DFS from index 0 with a mutable char array (or StringBuilder).
2If current char is a digit, append as-is and recurse to index + 1.
3If current char is a letter, recurse once with lowercase and once with uppercase (toggle with XOR 32 or ToLower/ToUpper).
4When index == length, add the current string to results.

Example Walkthrough

Input: s = "a1b2"

1.Branch a → A; digit 1 fixed; branch b → B; digit 2 fixed.
2.Four combinations: a1b2, a1B2, A1b2, A1B2.

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

Common Pitfalls

•Do not branch on digits — only letters double the search tree.
•Total combinations up to 2^(number of letters) — fine for small inputs.
•Copy the char array when branching if using shared mutable state.

784.cs

// Approach: DFS backtracking; at each letter position branch into both lowercase and uppercase variants.
// Time: O(2^n) Space: O(2^n)

public class Solution
{
    public IList<string> LetterCasePermutation(string s)
    {
        List<string> ans = new List<string>();
        Dfs(new StringBuilder(s), 0, ans);
        return ans;
    }

    private void Dfs(StringBuilder sb, int i, List<string> ans)
    {
        if (i == sb.Length)
        {
            ans.Add(sb.ToString());
            return;
        }
        if (char.IsDigit(sb[i]))
        {
            Dfs(sb, i + 1, ans);
            return;
        }

        sb[i] = char.ToLower(sb[i]);
        Dfs(sb, i + 1, ans);
        sb[i] = char.ToUpper(sb[i]);
        Dfs(sb, i + 1, ans);
    }
}

Was this solution helpful?