LeetCode 784 Letter Case Permutation - Example and Complexity Analysis

Trace "a1b2".

Start: current = "". Index 0 ('a' is letter): Branch 1: current = "a" Index 1 ('1' is digit): current = "a1" Index 2 ('b' is letter): Branch: "a1b" and "a1B" Index 3 ('2' is digit): "a1b2" and "a1B2" Branch 2: current = "A" Index 1 ('1'): current = "A1" Index 2 ('b'): Branch: "A1b" and "A1B" Index 3: "A1b2" and "A1B2"

Result: ["a1b2", "a1B2", "A1b2", "A1B2"].

If $k$ letters in string of length $n$, there are $2^k$ results. Each takes $O(n)$ to build. Total: $O(n \cdot 2^k)$.