Case-Flipped Passwords
EasyBacktracking
Problem
A user remembers their password s but not which letters were capitalised. Digits are certain; every letter could have been typed in lower or upper case.
Return every string you get by choosing a case for each letter of s, in any order.
Example 1
- Input:
- s = "a1b"
- Output:
- ["a1b", "a1B", "A1b", "A1B"]
Two letters, two cases each: 4 candidates. The digit 1 never changes.
Example 2
- Input:
- s = "7"
- Output:
- ["7"]
Constraints
- 1 ≤ s.length ≤ 12
- s contains only English letters and digits.
Hint
Show the first hint
Walk the string; each position contributes one or two options.
Walkthrough
How to approach it
01Clarify before coding
- Can the input already contain capitals? Yes; 'Zz' still yields four variants.
- Are duplicates possible in the output? No: two variants differ at the first letter where their cases differ.
- Does the output order matter? No.
02Brute force
Count the L letters, loop a mask over 0..2^L - 1 and build one string per mask, upper-casing letters whose bit is set.
Cost: O(n · 2^L), already optimal in output size; the recursive version is shown because it is the template for the harder problems in this topic.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.