Flip Letter Case Variants
Problem
A string mixes letters and digits. Every letter may be written in lowercase or in uppercase, while digits never change. Return every string you can produce this way. List them so that, for each letter from left to right, the lowercase choice comes before the uppercase one.
Examples
Input: s = "a1b"
Output: ["a1b", "a1B", "A1b", "A1B"]
Why: two letters, two choices each, four stringsInput: s = "3Z"
Output: ["3z", "3Z"]
Why: the letter's original case does not matter, both forms are listedInput: s = "42"
Output: ["42"]
Why: edge case, with no letters there is exactly one string, the input itselfHints
0 / 3
Walk the string one position at a time and ask how many options each position really has. Digits and letters answer that question differently.
This is a decision tree where letters split into two branches and digits pass straight through. The number of leaves is two to the number of letters.
Recurse on the position. At a letter, write its lowercase form into a shared buffer and recurse, then overwrite it with the uppercase form and recurse again. At a digit, just recurse. When the position reaches the end, record the joined buffer.
Solution
Each letter is an include-or-exclude style decision with exactly two branches, and each digit is a level with a single branch, so the recursion depth is the string length and the leaves are the answers. A single buffer holds the current string; each branch overwrites its own position before going deeper, which is why no explicit undo step is needed. Trying the lowercase form first gives the required order. With L letters in a string of length n there are 2 to the L results of length n, so time is O(n times 2 to the L) and the recursion depth is O(n).
def case_variants(s):
out, path = [], list(s)
def build(i):
if i == len(s): # every position is decided
out.append("".join(path))
return
if s[i].isalpha():
for ch in (s[i].lower(), s[i].upper()): # two branches
path[i] = ch # overwriting doubles as the undo
build(i + 1)
else:
build(i + 1) # a digit has a single branch
build(0)
return out
print(case_variants("a1b")) # -> ['a1b', 'a1B', 'A1b', 'A1B']
print(case_variants("3Z")) # -> ['3z', '3Z']
print(case_variants("42")) # -> ['42']Stuck on the idea rather than the code? Subsets covers it.