How do you approach Letter Case Permutation?

At each position, branch into lowercase and uppercase if it is a letter; otherwise keep the digit.

What are common mistakes on Letter Case Permutation?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

← Back to problems

Letter Case Permutation

MediumAlgorithms

Description

Given a string `s`, you may transform each **letter** to lowercase or uppercase (digits stay unchanged). Return a list of all strings that can be created this way. Results follow the order in which choices are explored (lowercase before uppercase at each letter).

Example 1

Input: s = "a1b2"

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

Explanation: Each letter toggles case independently.

Constraints

- 1 <= s.length <= 12 - s consists of letters and digits

Letter Case Permutation: approach, complexity and pitfalls

A medium backtracking problem, graded against 3 test cases (1 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 2-step hint ladder

At each position, branch into lowercase and uppercase if it is a letter; otherwise keep the digit.
Lowercase first then uppercase to match the expected ordering.

The optimal approach

Show the approach: The approach

Binary backtracking over letters. Walk the string; for a digit, recurse without branching. For a letter, set it lowercase and recurse, then uppercase and recurse. Record the string when you pass the end.

Time: O(2ᴸ·n) where L is the letter count. Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.