Letter Case Permutation

📋

Problem

Imagine you are designing a username generator that can create all possible variations of a string by toggling the case of its letters, helping users find unique but related usernames.

Given a string s, you can transform every letter individually to be lowercase or uppercase to create new strings. Return a list of all possible strings we could create. Digits remain unchanged.

1 ≤ s.length ≤ 12s consists of only letters or digits.

Edge cases: Empty string → [] or [''] depending on interpretationString with no letters (e.g., '1234') → ['1234'] onlyString with all letters (e.g., 'abc') → all 2^3 = 8 permutations

</>

IDE

def letterCasePermutation(s: str) -> list:public List<String> letterCasePermutation(String s)vector<string> letterCasePermutation(string s)function letterCasePermutation(s)

def letterCasePermutation(s: str) -> list:
    # Write your solution here
    pass

class Solution {
    public List<String> letterCasePermutation(String s) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> letterCasePermutation(string s) {
    // Write your solution here
    return {};
}

function letterCasePermutation(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: a1b2Only returning original string without toggling letter cases.✅ Add recursive calls to toggle each letter's case, exploring both lowercase and uppercase branches.

Wrong: a1b2A1b2Toggling only the first letter and not subsequent letters.✅ Ensure recursion continues toggling case for all letters, not just the first.

Wrong: Returning empty list for empty input instead of [''].✅ Add base case to return [''] when input string is empty.

Wrong: 3Z43z43Z4Duplicated outputs or toggling digits incorrectly.✅ Do not toggle digits; add digits as-is and toggle only letters.

Wrong: a1b2a1B2A1b2Missing some permutations due to incomplete recursion branches.✅ Ensure both lowercase and uppercase branches are explored for every letter.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Think about how your code handles uppercase letters and digits distinctly.

Consider the exponential complexity and optimize your recursion and string operations.

t1_01basic

Input{"s":"a1b2"}

Expected["a1b2","a1B2","A1b2","A1B2"]

⏱ Performance - must finish in 2000ms

For each letter, we choose lowercase or uppercase, digits stay the same. So 'a' → 'a' or 'A', 'b' → 'b' or 'B'.

💡 Consider each letter as a branching point with two choices: lowercase or uppercase.

💡 Use backtracking to explore all combinations by toggling case only for letters.

💡 Append the current path to results when the end of the string is reached.

Why it failed: Failed to generate all case permutations or missed toggling letter cases. Fix by ensuring both lowercase and uppercase branches are explored for letters.

✓ Correctly generates all permutations by toggling letter cases.

t1_02basic

Input{"s":"3z4"}

Expected["3z4","3Z4"]

⏱ Performance - must finish in 2000ms

Only one letter 'z' toggles case; digits remain unchanged.

💡 Check if your code correctly handles strings with digits and letters mixed.

💡 Ensure digits are added as-is without toggling case.

💡 Toggle case only for letters and generate all combinations.

Why it failed: Incorrect output due to toggling digits or ignoring letter case toggling. Fix by skipping digits and toggling only letters.

✓ Correctly handles mixed digits and letters with proper case toggling.

t2_01edge

Input{"s":""}

Expected[""]

⏱ Performance - must finish in 2000ms

Empty string input should return a list with an empty string as the only permutation.

💡 Consider the base case when the input string is empty.

💡 Your recursion should handle zero-length input by returning a list with an empty string.

💡 Return [''] when input is empty to represent the single valid permutation.

Why it failed: Returned empty list instead of [''] for empty input. Fix by adding base case returning [''] when input is empty.

✓ Correctly returns [''] for empty input.

t2_02edge

Input{"s":"7"}

Expected["7"]

⏱ Performance - must finish in 2000ms

Single digit input returns itself as the only permutation.

💡 Check handling of single-character strings that are digits.

💡 Digits should not be toggled; return the string as-is.

💡 Ensure single-character digit input returns a list with that digit.

Why it failed: Incorrectly toggled digit or returned empty list for single digit input. Fix by treating digits as fixed characters.

✓ Correctly returns single digit string as the only permutation.

t2_03edge

Input{"s":"abc"}

Expected["abc","abC","aBc","aBC","Abc","AbC","ABc","ABC"]

⏱ Performance - must finish in 2000ms

All letters input generates all 2^3 = 8 permutations by toggling each letter's case.

💡 For all-letter strings, expect 2^length permutations.

💡 Verify your recursion explores both lowercase and uppercase for every letter.

💡 Check that no permutations are missing or duplicated.

Why it failed: Missed some permutations or duplicated outputs for all-letter input. Fix by ensuring full binary branching on each letter.

✓ Correctly generates all 8 permutations for three-letter input.

t3_01corner

Input{"s":"a1B"}

Expected["a1b","a1B","A1b","A1B"]

⏱ Performance - must finish in 2000ms

Mixed case input with digits; output must toggle case of letters regardless of original case.

💡 Check if your code toggles case only from lowercase to uppercase or also uppercase to lowercase.

💡 Ensure toggling is symmetric: both lowercase and uppercase versions are generated for letters.

💡 Convert letters to both cases regardless of original case to generate all permutations.

Why it failed: Output missing toggled lowercase versions for originally uppercase letters. Fix by toggling both lowercase and uppercase for all letters.

✓ Correctly toggles case for letters regardless of original case.

t3_02corner

Input{"s":"1234"}

Expected["1234"]

⏱ Performance - must finish in 2000ms

String with no letters returns only the original string.

💡 Verify that digits are never toggled or changed.

💡 Check that your code does not generate extra permutations when no letters exist.

💡 Return the original string as the only permutation if no letters are present.

Why it failed: Generated extra permutations or empty output for all-digit input. Fix by skipping toggling when no letters are present.

✓ Correctly returns single permutation for all-digit input.

t3_03corner

Input{"s":"a1b2c3d4e5f6"}

Expected["a1b2c3d4e5f6","a1b2c3d4e5F6","a1b2c3d4E5f6","a1b2c3d4E5F6","a1b2c3D4e5f6","a1b2c3D4e5F6","a1b2c3D4E5f6","a1b2c3D4E5F6","a1b2C3d4e5f6","a1b2C3d4e5F6","a1b2C3d4E5f6","a1b2C3d4E5F6","a1b2C3D4e5f6","a1b2C3D4e5F6","a1b2C3D4E5f6","a1b2C3D4E5F6","a1B2c3d4e5f6","a1B2c3d4e5F6","a1B2c3d4E5f6","a1B2c3d4E5F6","a1B2c3D4e5f6","a1B2c3D4e5F6","a1B2c3D4E5f6","a1B2c3D4E5F6","a1B2C3d4e5f6","a1B2C3d4e5F6","a1B2C3d4E5f6","a1B2C3d4E5F6","a1B2C3D4e5f6","a1B2C3D4e5F6","a1B2C3D4E5f6","a1B2C3D4E5F6","A1b2c3d4e5f6","A1b2c3d4e5F6","A1b2c3d4E5f6","A1b2c3d4E5F6","A1b2c3D4e5f6","A1b2c3D4e5F6","A1b2c3D4E5f6","A1b2c3D4E5F6","A1b2C3d4e5f6","A1b2C3d4e5F6","A1b2C3d4E5f6","A1b2C3d4E5F6","A1b2C3D4e5f6","A1b2C3D4e5F6","A1b2C3D4E5f6","A1b2C3D4E5F6","A1B2c3d4e5f6","A1B2c3d4e5F6","A1B2c3d4E5f6","A1B2c3d4E5F6","A1B2c3D4e5f6","A1B2c3D4e5F6","A1B2c3D4E5f6","A1B2c3D4E5F6","A1B2C3d4e5f6","A1B2C3d4e5F6","A1B2C3d4E5f6","A1B2C3d4E5F6","A1B2C3D4e5f6","A1B2C3D4e5F6","A1B2C3D4E5f6","A1B2C3D4E5F6"]

⏱ Performance - must finish in 2000ms

Long mixed string with letters and digits; must toggle case for all 6 letters, generating 2^6=64 permutations.

💡 Check that your solution scales correctly with multiple letters interspersed with digits.

💡 Verify that toggling is applied only to letters and all combinations are generated.

💡 Use backtracking or iterative BFS to generate all 64 permutations for 6 letters.

Why it failed: Missed some permutations or toggled digits incorrectly in long mixed input. Fix by toggling only letters and exploring all branches.

✓ Correctly generates all 64 permutations for 6-letter mixed input.

t4_01performance

Input{"s":"a1b2c3d4e5f6"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=12 with 6 letters; 2^6=64 permutations expected. Algorithm must run in O(2^k * n) time within 2 seconds.

💡 The complexity is exponential in the number of letters, not total length.

💡 Use efficient backtracking with pruning and in-place modifications.

💡 Avoid unnecessary string copies to meet time constraints.

Why it failed: TLE due to exponential complexity in number of letters. Fix by using backtracking with pruning and efficient string handling.

✓ Algorithm runs within time limit confirming O(2^k * n) complexity.

Practice

1. Consider the following Python function implementing backtracking with bitmask memoization for partitioning an array into k equal sum subsets. Given nums = [4, 3, 2, 3, 5, 2, 1] and k = 4, what is the final return value of canPartitionKSubsets(nums, k)?

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target sum

   Total sum is 4+3+2+3+5+2+1=20, target per subset = 20/4=5.

2. Step 2: Trace backtracking with sorted nums

   Sorted nums: [5,4,3,3,2,2,1]. The algorithm finds subsets: {5}, {4,1}, {3,2}, {3,2} all summing to 5, so returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All subsets sum to target, so partition possible [OK]

Hint: Sum divisible by k and backtracking finds valid subsets [OK]

Common Mistakes:

• Miscounting sum or target
• Assuming no solution due to order

2. You need to generate all possible subsets of a given set of distinct integers. Which algorithmic approach guarantees enumerating every subset exactly once, including the empty subset, without missing or duplicating any subset?

easy

A. Greedy algorithm that picks elements based on a heuristic to maximize subset size

B. Dynamic programming approach that builds subsets by summing elements to target values

C. Backtracking with include/exclude decisions at each element to explore all subset combinations

D. Sorting the array and then using two pointers to find pairs that form subsets

Solution

1. Step 1: Understand problem requirements

   The problem requires enumerating all subsets, which means exploring all combinations of including or excluding each element.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude decisions systematically explores all subsets without duplication or omission, including the empty subset.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking ensures all subsets are generated [OK]

Hint: Include/exclude backtracking covers all subsets [OK]

Common Mistakes:

• Confusing subset generation with greedy or DP sum problems

3. The following code attempts to find the largest divisible subset but contains a subtle bug. Identify the line with the bug.

def largestDivisibleSubset(nums):
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[j] % nums[i] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

medium

A. Line with 'result.append(nums[max_index])'

B. Line with 'dp = [1] * n'

C. Line with 'max_index = 0'

D. Line with 'if nums[j] % nums[i] == 0:'

Solution

1. Step 1: Check divisibility condition

   The condition should be nums[i] % nums[j] == 0 because we want to check if current number is divisible by a smaller number.

2. Step 2: Understand impact of bug

   Using nums[j] % nums[i] == 0 reverses the divisibility logic, causing incorrect dp updates and wrong subsets.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct divisibility check is crucial for correctness [OK]

Hint: Divisibility check direction matters [OK]

Common Mistakes:

• Swapping divisor and dividend in modulo check
• Not sorting input before DP
• Incorrect subset reconstruction

4. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium

A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset

B. O(2^n) because there are 2^n subsets and each subset is generated in constant time

C. O(n^2) because of nested loops over n elements

D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements

Solution

1. Step 1: Identify outer loop complexity

   The outer loop runs 2^n times, once per subset mask.

2. Step 2: Identify inner loop complexity

   For each mask, the inner loop iterates n times to check each bit.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is 2^n * n due to mask and bit checks [OK]

Hint: Each subset requires checking n bits -> O(n*2^n) [OK]

Common Mistakes:

• Assuming subset generation is O(2^n) ignoring bit checks
• Confusing n^2 with 2^n * n

5. Suppose the problem is modified so that numbers 1 to 9 can be reused any number of times in combinations summing to n with size k. Which change to the backtracking algorithm correctly handles this variant?

hard

A. Add a visited set to prevent reusing numbers and keep backtrack(i + 1, comb, total + i)

B. Keep the recursive call as backtrack(i + 1, comb, total + i) but allow duplicates in the result

C. Change the recursive call to backtrack(i, comb, total + i) to allow reuse of the same number i

D. Use a dynamic programming approach instead of backtracking to handle reuse efficiently

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means the same number can be chosen multiple times, so next recursion should start at current number i, not i+1.

2. Step 2: Modify recursive call

   Change backtrack(i + 1, ...) to backtrack(i, ...) to allow repeated picks of i.

3. Step 3: Confirm correctness

   This change correctly explores combinations with repeated numbers without duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Recursing with start=i enables reuse of number i [OK]

Hint: Reuse requires recursive calls with start index unchanged [OK]

Common Mistakes:

• Not changing start index to allow reuse
• Allowing duplicates by mistake
• Switching to DP unnecessarily