Letter Case Permutation - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: Given a string containing letters and digits, generate every possible string formed by toggling the case of each alphabetic character. Digits stay unchanged. If the input contains k letters, the output contains 2^k permutations.
Approach 1: Backtracking (Time: O(2^k * n), Space: O(2^k * n))
This approach treats the problem as a decision tree. For every character, you decide how it appears in the current permutation. Digits have only one choice, but letters branch into two choices: lowercase and uppercase. Use a recursive backtracking function that builds the string character by character. When the index reaches the end of the string, push the constructed permutation to the result list.
The key idea is exploring both case options whenever you encounter an alphabetic character. Each recursive call modifies the current path and backtracks afterward to explore the alternative branch. Because every letter doubles the number of possibilities, the algorithm generates 2^k permutations, each requiring up to n work to build.
This method is the most intuitive if you already know backtracking. It mirrors the permutation generation pattern used in many interview problems and works well for small-to-medium strings.
Approach 2: Iterative Bit Manipulation (Time: O(2^k * n), Space: O(2^k * n))
Instead of recursion, represent each case combination using a bitmask. First identify the indices of alphabetic characters in the string. If there are k letters, iterate through integers from 0 to 2^k - 1. Each bit in the number determines whether a specific letter becomes lowercase or uppercase.
For every mask, create a character array from the original string. Iterate through the stored letter positions and toggle case based on the corresponding bit value. A bit value of 1 may represent uppercase and 0 lowercase. After applying all decisions, convert the array back to a string and append it to the result list.
This method replaces recursion with binary enumeration. It works well when you want a predictable iterative pattern and demonstrates how bit manipulation can encode combinational choices efficiently.
Recommended for interviews: Backtracking is typically the expected explanation because it clearly shows how you explore permutations in a search tree. Interviewers like seeing how you branch on each character and revert state. The bitmask solution is equally optimal but more of an optimization mindset. Mentioning both shows strong understanding of string enumeration problems.
Approach 1: Backtracking Approach
In this approach, we use a backtracking algorithm to generate all possible letter case permutations for each character in the string. We iterate over each character and decide to either transform it (if it's a letter) or leave it unchanged. By following this approach, we can explore all possible combinations.
The C solution employs a recursive backtracking method to explore each character's transformation possibilities. It toggles the case of letters using the XOR operation and makes recursive calls to explore each possibility. The program handles string duplication and manages a list of results dynamically.
Complexity
Time Complexity: O(2^n), where n is the number of letters in the string.
Space Complexity: O(2^n) for storing the results.
Approach 2: Iterative Bit Manipulation
This approach utilizes bit manipulation to generate permutations. Each letter can be either in uppercase or lowercase, and we represent each possibility with bits. By iterating through all possible binary combinations (where a bit signifies changing the case of a letter), we construct the result directly.
The Python solution calculates all possible transformations using bit manipulation for the powerset of letters. It iteratively transforms characters based on the current state of bit masking and then constructs each permutation by appending to the result list.
Code
Python
JavaScript
Complexity
Time Complexity: O(2^n), where n is the number of letters since we iterate over each possible set of transformations.
Space Complexity: O(2^n) for storage of permutations.
Approach 3: DFS
Since each letter in s can be converted to uppercase or lowercase, we can use the DFS (Depth-First Search) method to enumerate all possible cases.
Specifically, traverse the string s from left to right. For each letter encountered, you can choose to convert it to uppercase or lowercase, and then continue to traverse the subsequent letters. When you reach the end of the string, you get a conversion scheme and add it to the answer.
The method of converting case can be implemented using bitwise operations. For a letter, the difference between the ASCII codes of its lowercase and uppercase forms is 32, so we can achieve case conversion by XORing the ASCII code of the letter with 32.
The time complexity is O(n times 2^n), where n is the length of the string s. For each letter, we can choose to convert it to uppercase or lowercase, so there are 2^n conversion schemes in total. For each conversion scheme, we need O(n) time to generate a new string.
Approach 4: Binary Enumeration
For a letter, we can convert it to uppercase or lowercase. Therefore, for each letter, we can use a binary bit to represent its conversion scheme, where 1 represents lowercase and 0 represents uppercase.
First, we count the number of letters in the string s, denoted as n. Then, there are 2^n conversion schemes in total. We can use each bit of a binary number to represent the conversion scheme of each letter, enumerating from 0 to 2^n-1.
Specifically, we can use a variable i to represent the current binary number being enumerated, where the j-th bit of i represents the conversion scheme of the j-th letter. That is, the j-th bit of i being 1 means the j-th letter is converted to lowercase, and 0 means the j-th letter is converted to uppercase.
The time complexity is O(n times 2^n), where n is the length of the string s. For each letter, we can choose to convert it to uppercase or lowercase, so there are 2^n conversion schemes in total. For each conversion scheme, we need O(n) time to generate a new string.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^n), where n is the number of letters in the string. |
| Iterative Bit Manipulation | Time Complexity: O(2^n), where n is the number of letters since we iterate over each possible set of transformations. |
| DFS | — |
| Binary Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^k * n) | O(2^k * n) | Best for interviews and recursive permutation problems |
| Iterative Bit Manipulation | O(2^k * n) | O(2^k * n) | When you prefer iterative enumeration using binary masks |
Video Solution
LEETCODE 784 (JAVASCRIPT) | LETTER CASE PERMUTATION • Andy Gala • 9,829 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Letter Case Permutation easy or hard?
How to solve Letter Case Permutation in O(n)?
What is the best approach for Letter Case Permutation?
What data structure is used in Letter Case Permutation?
What is the time complexity of Letter Case Permutation?
Letter Case Permutation Python or Java solution approach?
Is Letter Case Permutation asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Letter Case Permutation with our built-in code editor and test cases.
Practice on FleetCode