Letter Case Permutation
MedPrompt
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 we could create. Return the output in any order.
Example 1:
Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]Example 2:
Input: s = "3z4"
Output: ["3z4","3Z4"]
Constraints:
1 <= s.length <= 12sconsists of lowercase English letters, uppercase English letters, and digits.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iteratively builds the list of all possible permutations. It starts with a list containing just an empty string. Then, for each character in the input string, it expands the list of permutations. If the character is a letter, it doubles the size of the list by creating two new versions for each existing permutation (one with the lowercase letter, one with the uppercase). If it's a digit, it simply appends the digit to every existing permutation.
Algorithm
- Initialize a list of strings,
permutations, and add an empty string to it. - Iterate through each character
cof the input strings. - For each character, create a temporary list
newPermutations. - Iterate through each string
pcurrently in thepermutationslist. - If
cis a letter, add two new strings tonewPermutations:pwith the lowercase ofcappended, andpwith the uppercase ofcappended. - If
cis a digit, add one new string tonewPermutations:pwithcappended. - After processing all strings for the current character, replace
permutationswithnewPermutations. - After iterating through all characters of
s, thepermutationslist holds the final result.
Walkthrough
This method can be visualized as a Breadth-First Search (BFS) through the decision tree of possibilities. We maintain a list of all permutations generated so far. We process the input string character by character, and at each step i, we use the permutations of length i to generate all permutations of length i+1.
For example, with s = "a1b":
- Start with
permutations = [""]. - Process 'a':
permutationsbecomes["a", "A"]. - Process '1':
permutationsbecomes["a1", "A1"]. - Process 'b':
permutationsbecomes["a1b", "a1B", "A1b", "A1B"].
While conceptually simple, this implementation creates a new list and new strings at each step, which can be inefficient.
class Solution { public List<String> letterCasePermutation(String s) { List<String> permutations = new ArrayList<>(); if (s == null) { return permutations; } permutations.add(""); for (char c : s.toCharArray()) { List<String> newPermutations = new ArrayList<>(); for (String p : permutations) { if (Character.isLetter(c)) { newPermutations.add(p + Character.toLowerCase(c)); newPermutations.add(p + Character.toUpperCase(c)); } else { newPermutations.add(p + c); } } permutations = newPermutations; } return permutations; }}Complexity
Time
O(N * 2^L), where N is the length of the string and L is the number of letters. For each of the `N` characters, we iterate through the current list of permutations and create new strings. The total number of generated strings is proportional to `N * 2^L`.
Space
O(N * 2^L), where N is the length of the string and L is the number of letters. This is dominated by the space required to store the `2^L` output strings of length `N`. The intermediate list `newPermutations` also contributes to this.
Trade-offs
Pros
It's an iterative approach, so it avoids recursion and the risk of stack overflow.
The logic is straightforward and easy to follow.
Cons
Creating a new list (
newPermutations) in each iteration can lead to significant memory allocation and garbage collection overhead.String concatenation in a loop (
p + c) creates many intermediate string objects, which is inefficient.
This approach uses recursion with backtracking, which is a natural fit for permutation and combination problems. We traverse the string, and at each character, we make a decision. If the character is a letter, we explore two branches: one for its lowercase form and one for its uppercase form. If it's a digit, we only explore one path. This effectively performs a Depth-First Search (DFS) on the decision tree.
Algorithm
- Convert the input string
sto a character arraycharsfor efficient in-place modification. - Create a result list
result. - Define a recursive helper function,
backtrack(index). - Base Case: If
indexequals the length ofchars, it means a full permutation has been formed. Convert thecharsarray to a string and add it toresult. Then, return. - Recursive Step:
- Get the character
catchars[index]. - If
cis a letter:- Set
chars[index]to its lowercase version and make a recursive call:backtrack(index + 1). - Set
chars[index]to its uppercase version and make another recursive call:backtrack(index + 1).
- Set
- If
cis a digit:- Make a single recursive call:
backtrack(index + 1).
- Make a single recursive call:
- Get the character
- Start the process by calling
backtrack(0).
Walkthrough
The core idea is to build the permutations in place using a character array. A recursive function explores all possibilities by changing characters at the current position and then calling itself for the next position. After a recursive call returns (i.e., after exploring a branch), the state is implicitly restored because the subsequent recursive call will overwrite the character at the same position.
This in-place modification is more memory-efficient than creating new strings at each step of the recursion.
class Solution { public List<String> letterCasePermutation(String s) { List<String> result = new ArrayList<>(); backtrack(s.toCharArray(), 0, result); return result; } private void backtrack(char[] chars, int index, List<String> result) { if (index == chars.length) { result.add(new String(chars)); return; } char c = chars[index]; if (Character.isLetter(c)) { // Lowercase branch chars[index] = Character.toLowerCase(c); backtrack(chars, index + 1, result); // Uppercase branch chars[index] = Character.toUpperCase(c); backtrack(chars, index + 1, result); } else { // Digit branch backtrack(chars, index + 1, result); } }}Complexity
Time
O(N * 2^L). The recursion tree has `2^L` leaf nodes. At each leaf, we do O(N) work to create a new string. The total number of nodes in the tree is about `2 * 2^L`, and the work at each node is constant, leading to the overall complexity.
Space
O(N * 2^L). The output list requires this much space. The auxiliary space used by the recursion stack is O(N).
Trade-offs
Pros
The code is elegant and directly models the problem's recursive structure.
The in-place modification of a character array is very efficient in terms of auxiliary space (O(N) for the recursion stack).
Cons
Involves recursion, which adds function call overhead.
For extremely long strings (not the case here due to constraints), it could lead to a stack overflow error.
This clever approach maps each permutation to a unique integer. If there are L letters in the string, there are 2^L possible case combinations. We can iterate through numbers from 0 to 2^L - 1. Each number's binary representation (as a bitmask of length L) dictates the case for each letter in a specific permutation. For example, the k-th bit of the number can decide the case of the k-th letter in the string.
Algorithm
- First, count the number of letters,
L, in the input strings. - The total number of permutations is
total = 2^L. - Initialize an empty list
resultto store the final strings. - Loop with a counter
ifrom0tototal - 1. - For each
i, we will generate one unique permutation.- Create a
StringBuilder. - Initialize a
letter_bit_poscounter to0. - Iterate through the input string
scharacter by character. - If the character
cis a letter:- Check the
letter_bit_pos-th bit ofiusing(i >> letter_bit_pos) & 1. - If the bit is
1, append the uppercase version ofc. - If the bit is
0, append the lowercase version ofc. - Increment
letter_bit_pos.
- Check the
- If the character is a digit, append it as is.
- After building the string, add it to the
resultlist.
- Create a
- Return the
resultlist.
Walkthrough
We can directly generate each of the 2^L permutations without recursion. We loop 2^L times. In each iteration i, we construct the i-th permutation. The binary representation of i serves as a blueprint. For instance, if i is 5 (binary 101), it could mean the 1st letter is uppercase, 2nd is lowercase, and 3rd is uppercase. We iterate through the input string, and when we encounter a letter, we use the next available bit from our counter i to decide its case.
class Solution { public List<String> letterCasePermutation(String s) { int letterCount = 0; for (char c : s.toCharArray()) { if (Character.isLetter(c)) { letterCount++; } } int numPermutations = 1 << letterCount; List<String> result = new ArrayList<>(numPermutations); for (int i = 0; i < numPermutations; i++) { StringBuilder sb = new StringBuilder(); int letterIndex = 0; for (char c : s.toCharArray()) { if (Character.isLetter(c)) { // Check the bit for the current letter if (((i >> letterIndex) & 1) == 1) { sb.append(Character.toUpperCase(c)); } else { sb.append(Character.toLowerCase(c)); } letterIndex++; } else { sb.append(c); } } result.add(sb.toString()); } return result; }}Complexity
Time
O(N * 2^L). We have an outer loop that runs `2^L` times, and an inner loop that runs `N` times to build each string.
Space
O(N * 2^L). This is dominated by the storage for the result list. Auxiliary space is O(N) for the `StringBuilder`.
Trade-offs
Pros
Highly efficient iterative solution that avoids recursion overhead.
Uses fast bitwise operations.
The total number of permutations is known before the main loop begins.
Cons
The logic can be less intuitive to grasp compared to a direct backtracking approach.
It typically requires a pre-computation step to count the letters or find their indices.
Solutions
Solution
class Solution { private List < String > ans = new ArrayList <>(); private char [] t ; public List < String > letterCasePermutation ( String s ) { t = s . toCharArray (); dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i >= t . length ) { ans . add ( String . valueOf ( t )); return ; } dfs ( i + 1 ); if ( t [ i ] >= 'A' ) { t [ i ] ^= 32 ; dfs ( i + 1 ); } } }class Solution { public: vector < string > letterCasePermutation ( string s ) { vector < string > ans ; function < void ( int ) > dfs = [ & ]( int i ) { if ( i >= s . size ()) { ans . emplace_back ( s ); return ; } dfs ( i + 1 ); if ( s [ i ] >= 'A' ) { s [ i ] ^= 32 ; dfs ( i + 1 ); } }; dfs ( 0 ); return ans ; } };class Solution : def letterCasePermutation ( self , s : str ) -> List [ str ]: def dfs ( i ): if i >= len ( s ): ans . append ( '' . join ( t )) return dfs ( i + 1 ) if t [ i ]. isalpha (): t [ i ] = chr ( ord ( t [ i ]) ^ 32 ) dfs ( i + 1 ) t = list ( s ) ans = [] dfs ( 0 ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.