Letter Case Permutation
Generate every string from changing each letter's case with backtracking: each letter branches into lower and upper case, digits pass through.
Problem Understanding
Letter Case Permutation: given a string s of letters and digits, return every string you can make by changing each letter to lower or upper case, in any order.
Example: s = "a1b2" returns ["a1b2", "a1B2", "A1b2", "A1B2"].
The Intuition: A Binary Choice per Letter
Every letter is a yes/no choice (lower or upper), and every digit is fixed. That is a binary decision tree, explored with backtracking:
- At index
i, a digit has one child: move toi + 1. - A letter has two children: lower case, then upper case.
- A full path is one answer.
It is the same "choose for each position" shape as Subsets, where each element is in or out, and Letter Combinations of a Phone Number, where each digit has several letters.
Interactive Walkthrough
The string being built is shown with the current index filled; characters already fixed on this branch are tinted. Recorded strings collect beside it. Try Four letters to watch 16 strings appear.
Dry Run Table
Input: s = "a1b2"
| [0] a | [1] 1 | [2] b | [3] 2 | Result |
|---|---|---|---|---|
| a | 1 | b | 2 | a1b2 |
| a | 1 | B | 2 | a1B2 |
| A | 1 | b | 2 | A1b2 |
| A | 1 | B | 2 | A1B2 |
Answer: 4 strings (2 letters, 2² = 4).
The Solution Template
Backtracking over a mutable copy of the string. C sizes the result as 2^k up front.
Letter Case Permutation Code
1var letterCasePermutation = function(s) {2 const res = [], path = s.split('');3 const backtrack = (i) => {4 if (i === s.length) {5 res.push(path.join(''));6 return;7 }8 if (/[a-z]/i.test(s[i])) {9 path[i] = s[i].toLowerCase();10 backtrack(i + 1);11 path[i] = s[i].toUpperCase();12 backtrack(i + 1);13 } else {14 backtrack(i + 1);15 }16 };17 backtrack(0);18 return res;19};
Edge Cases & Common Mistakes
- No letters: the only result is the string itself.
- Upper-case input letters: set both cases explicitly instead of toggling, so
"C"still gives"c"and"C". - Branching on digits: produces duplicate strings; digits have only one option.
- Sharing one mutable buffer: fine in this template: every letter position is set again on each branch before the string is recorded, so leftovers from an earlier branch never leak in.
- Order: any order is accepted; this template lists lower-case branches first.
Summary
Walk the string by index. Digits pass straight through; each letter branches into lower and upper case. Record the string when the index reaches the end. k letters give 2^k strings, in O(n · 2^k) time.
More practice: DSA interview questions with answers · patterns cheat sheet