502. Letter Case Permutation
You are given a string s made of English letters and digits. Every letter can independently be written in lowercase or uppercase; digits stay as they are. Build the list of every string obtainable this way and return it.
A string with k letters produces exactly 2^k variants.
The output order is fixed. Process the characters left to right and, at every letter, take the lowercase form before the uppercase form — the order a depth-first search produces when it always branches lowercase-first. Equivalently: the leftmost letter is the most significant bit, with lowercase = 0 and uppercase = 1, and you count from 0 to 2^k − 1.
Example 1:
Input: s = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
Explanation: Two letters ('a' and 'b') give 2² = 4 variants. Counting with the leftmost letter as the most significant bit: aa→a1b2, aB→a1B2, Ab→A1b2, AB→A1B2.
Example 2:
Input: s = "3z4"
Output: ["3z4", "3Z4"]
Explanation: Only one letter, so there are 2¹ = 2 variants, lowercase form first.
Constraints:
- 1 ≤ s.length ≤ 12
- s consists of English letters (a-z, A-Z) and digits (0-9) only
Hints:
Each letter is an independent yes/no choice (lowercase or uppercase), so the answers form a full binary tree with 2^k leaves. You need a systematic way to visit every leaf exactly once.
Backtrack: at position i, a digit is appended and you recurse once; a letter recurses twice — append the lowercase form, recurse, undo, then append the uppercase form, recurse, undo. Branching lowercase-first yields exactly the required order.
Bit-manipulation alternative: number the letters left to right and loop mask = 0 … 2^k − 1; bit b of the mask (leftmost letter = most significant) says whether letter b is uppercase. Counting up reproduces the same order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "a1b2"
Expected output: ["a1b2", "a1B2", "A1b2", "A1B2"]