Coding Interview PatternsLetter Case Permutation
MediumSubsets
Letter Case Permutation
Explanation & Solution
Description
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings you could create. Return the output in any order.
Input: s = "a1b2"
Output:["A1B2","A1b2","a1B2","a1b2"]
0
A1B2
1
A1b2
2
a1B2
3
a1b2
Explanation: Each letter ('a' and 'b') can independently be uppercase or lowercase.
Constraints
1 <= s.length <= 12sconsists of lowercase English letters, uppercase English letters, and digits
Approach
Subsets pattern
1. Process Each Character
- Iterate through the string character by character using an index
- At each position, determine whether the character is a letter or a digit
2. Branch on Letters
- If the character is a letter, create two branches:
- One with the character in lowercase
- One with the character in uppercase
- This doubles the number of permutations at each letter position
3. Pass Through Digits
- If the character is a digit, simply append it and continue
- Digits do not create new branches since they have no case
4. Collect at Base Case
- When the index reaches the end of the string, add the constructed string to the result
- Every path through the recursion tree produces one valid permutation
5. Sort and Return
- Sort all permutations lexicographically for consistent output
- Return the complete list
Key Insight
- Each letter doubles the number of results, while digits have no effect on branching
Time
O(n * 2^L) where L is the number of letters in the string and n is the string lengthSpace
O(n) for recursion depth, plus O(n * 2^L) for storing resultsVisualization
Input:
[a, 1, b, 2]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps