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 code implementing the optimal backtracking with bitmask and memoization approach for the Matchsticks to Square problem. Given the input [1,1,2,2,2], what is the final return value of makesquare([1,1,2,2,2])?

easy

A. True

B. Depends on the order of matchsticks

C. Raises an exception due to index error

D. False

Solution

1. Step 1: Calculate total and side length

   Total = 1+1+2+2+2 = 8, side = 8/4 = 2.

2. Step 2: Trace backtracking calls

   Sorted sticks: [2,2,2,1,1]. The algorithm tries to form sides of length 2. It can form three sides with three 2's, and the last side with two 1's. Hence, returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum divisible by 4 and sticks fit sides exactly [OK]

Hint: Sum divisible by 4 and sticks fit sides exactly [OK]

Common Mistakes:

• Forgetting to sort and prune
• Assuming order affects result
• Miscounting sides formed

2. What is the time complexity of the backtracking solution with frequency counting for the Combination Sum (Reuse Allowed) problem, where N is the number of candidates, T is the target, and M is the minimum candidate value?

medium

A. O(N * T) because each candidate is tried once for each target value.

B. O(2^N) because each candidate can be either included or excluded once.

C. O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M.

D. O(T^N) because for each target value, all candidates are tried in all combinations.

Solution

1. Step 1: Identify recursion depth and branching factor

   The recursion depth is roughly T/M because the smallest candidate can be used up to T/M times. At each level, up to N candidates are considered with multiple counts.

2. Step 2: Calculate total number of recursive calls

   Each candidate can be chosen 0 to max_use times, leading to branching factor roughly N^(T/M + 1). This exponential complexity dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exponential branching with depth proportional to T/M matches O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M. [OK]

Hint: Exponential in target divided by smallest candidate [OK]

Common Mistakes:

• Confusing DP complexity with backtracking
• Ignoring exponential branching due to reuse

3. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

4. Identify the bug in the following code snippet for counting max bitwise-OR subsets:

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(0, 1 << n):  # Note: starts from 0
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

medium

A. The count variable should be reset inside the inner loop

B. The OR operation should be replaced with AND

C. The loop should start from 1 to exclude empty subset

D. max_or should be initialized to -1 instead of 0

Solution

1. Step 1: Identify that mask=0 represents empty subset

   Empty subset OR is 0, which is usually not counted as a valid subset.

2. Step 2: Recognize that including empty subset inflates count incorrectly

   Starting from mask=0 causes counting empty subset, leading to wrong final count.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exclude empty subset by starting mask from 1 -> correct counting [OK]

Hint: Empty subset mask=0 must be excluded to avoid incorrect counts [OK]

Common Mistakes:

• Counting empty subset as valid
• Incorrect initialization of max_or

5. Suppose the problem is modified so that elements can be reused multiple times in the subset (i.e., the subset can contain duplicates). Which modification to the algorithm is necessary to correctly find the largest divisible subset under this new constraint?

hard

A. Modify DP to consider all previous elements including i itself, allowing repeated use, and remove early break

B. Switch to a graph cycle detection algorithm to handle repeated elements

C. Use the same DP approach but allow dp[i] to consider dp[i] itself for reuse, enabling cycles

D. Use a greedy approach picking the largest element repeatedly until no more divisible

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means elements can appear multiple times, so dp must consider extending from the same element multiple times.

2. Step 2: Modify DP logic

   DP inner loop must consider j ≤ i (including i itself) and remove early break because sorted order no longer guarantees divisibility breaks.

3. Step 3: Reject incorrect options

   Greedy fails to find longest chain; graph cycle detection is unnecessary; naive DP without modification misses reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP adjusted for reuse and no early break handles duplicates [OK]

Hint: Reuse requires DP to consider self and no early break [OK]

Common Mistakes:

• Using original DP without changes leads to incorrect results
• Trying greedy approach which fails on complex divisibility
• Confusing graph cycles with DP chains