Watch 10 video solutions for Letter Case Permutation, a medium level problem involving String, Backtracking, Bit Manipulation. This walkthrough by Hua Hua has 10,046 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 12s consists of lowercase English letters, uppercase English letters, and digits.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 | 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 |