Backtracking — Letter Case Permutation
↗ LeetCode: Letter Case Permutation · Medium · pattern chapter →
Asked atMetaAmazonGoogle
Return every case variant of letters (digits stay).
Example 1 — s="a1b2" → ["a1b2","a1B2","A1b2","A1B2"]Example 2 — s="3z4" → ["3z4","3Z4"]Example 3 — s="12345" → ["12345"] (no letters — one variant)
Constraints — 1 ≤ n ≤ 12. That constraint gives 2¹² = 4096 upper bound on output size — trivially fast. Brute generates all 2ⁿ case-flip strings then filters — same complexity as the backtracking approach: O(2ⁿ) = ~10⁶ ops at n=20 for output size that many strings.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — DFS with two branches per letter (canonical)
java
List<String> letterCasePermutation(String s) {
List<String> out = new ArrayList<>();
dfs(s.toCharArray(), 0, out);
return out;
}
void dfs(char[] a, int i, List<String> out) {
if (i == a.length) { out.add(new String(a)); return; }
dfs(a, i + 1, out);
if (Character.isLetter(a[i])) {
a[i] ^= 32;
dfs(a, i + 1, out);
a[i] ^= 32;
}
}Execution Trace
Step 1 / 3Initialize scan.
Approach 2 — Iterative bit-enumeration
Count L letters; for mask 0..2^L-1 flip corresponding cases.
Complexity — Time O(n · 2^L); Space O(n) recursion.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DFS | O(n · 2^L) | O(n) | canonical |
| Bit enumeration | O(n · 2^L) | O(1) | iterative |
When to use which
- Small L → either.
- Case with constraints → DFS + prune.
AI Study CompanionBeta
Related problems
Was this page helpful?