Letter Case Permutation

▶

Steps

setup

Initialize / Setup

The input string 'a1b2' is converted into a character array ['a', '1', 'b', '2']. The results list is initialized empty. The backtracking starts at index 0.

💡 Converting to a character array allows in-place modification of letters, which is efficient for exploring case permutations.

Line:

res = []
arr = list(s)
backtrack(0)

💡 Setup prepares the data structures and starts the recursive exploration from the first character.

traverse

Process index 0: letter 'a' lowercase branch

At index 0, the character 'a' is a letter. The algorithm sets it to lowercase 'a' and recurses to index 1.

💡 Choosing lowercase first is a systematic way to explore all letter case options in order.

Line:

arr[i] = arr[i].lower()
backtrack(i + 1)

💡 The algorithm explores the lowercase option before uppercase to ensure all permutations are covered.

traverse

Process index 1: digit '1', skip case change

At index 1, the character '1' is a digit. The algorithm skips case changes and recurses directly to index 2.

💡 Digits do not have case variants, so the algorithm moves forward without branching here.

Line:

if arr[i].isdigit():
    backtrack(i + 1)

💡 Digits are handled efficiently by skipping unnecessary recursive branches.

traverse

Process index 2: letter 'b' lowercase branch

At index 2, the character 'b' is a letter. The algorithm sets it to lowercase 'b' and recurses to index 3.

💡 Again, the algorithm explores the lowercase option first for this letter.

Line:

arr[i] = arr[i].lower()
backtrack(i + 1)

💡 The recursion tree branches at each letter to explore both cases systematically.

traverse

Process index 3: digit '2', skip case change

At index 3, the character '2' is a digit. The algorithm skips case changes and recurses to index 4 (end).

💡 Digits are always passed through without branching, simplifying the recursion at these positions.

Line:

if arr[i].isdigit():
    backtrack(i + 1)

💡 Digits act as fixed characters in all permutations.

reconstruct

Base case reached: add 'a1b2' to results

Index 4 equals the length of the array, so the current permutation 'a1b2' is complete and added to the results list.

💡 The base case collects a valid answer formed by the choices made along the path.

Line:

if i == len(arr):
    res.append(''.join(arr))
    return

💡 Each leaf node in the recursion tree corresponds to a complete valid permutation.

traverse

Backtrack to index 3: uppercase branch for 'b'

Backtracking to index 3, the algorithm now sets 'b' to uppercase 'B' and recurses to index 4 again.

💡 Backtracking reverts previous choices and explores the alternative uppercase branch for the letter.

Line:

arr[i] = arr[i].upper()
backtrack(i + 1)

💡 Backtracking enables exploring all letter case permutations by reverting and changing choices.

reconstruct

Base case reached: add 'a1B2' to results

At index 4, the permutation 'a1B2' is complete and added to the results list.

💡 Another valid permutation is collected after exploring the uppercase branch.

Line:

if i == len(arr):
    res.append(''.join(arr))
    return

💡 The recursion tree's leaves accumulate all valid permutations.

backtracking

Backtrack to index 2: revert 'b' and backtrack to index 0 uppercase branch

Backtracking reverts 'b' to original and returns to index 0 to explore uppercase branch for 'a'.

💡 Reverting changes is essential to explore alternative branches without corrupting the array state.

Line:

arr[i] = s[i]  # revert to original
arr[0] = arr[0].upper()
backtrack(1)

💡 Backtracking restores state to explore new branches cleanly.

traverse

Process index 1: digit '1', skip case change (uppercase 'a' branch)

At index 1, digit '1' is encountered again; the algorithm skips case changes and recurses to index 2.

💡 Digits are always skipped regardless of letter case choices at other indices.

Line:

if arr[i].isdigit():
    backtrack(i + 1)

💡 Digits do not add complexity to the recursion tree.

traverse

Process index 2: letter 'b' lowercase branch (uppercase 'a' branch)

At index 2, the algorithm sets 'b' to lowercase and recurses to index 3.

💡 The branching pattern repeats for each letter regardless of previous letter case choices.

Line:

arr[i] = arr[i].lower()
backtrack(i + 1)

💡 Each letter independently branches into lowercase and uppercase options.

traverse

Process index 3: digit '2', skip case change (uppercase 'a', lowercase 'b' branch)

At index 3, digit '2' is encountered; the algorithm skips case changes and recurses to index 4.

💡 Digits are consistently skipped in all branches.

Line:

if arr[i].isdigit():
    backtrack(i + 1)

💡 Digits do not affect branching complexity.

reconstruct

Base case reached: add 'A1b2' to results

At index 4, the permutation 'A1b2' is complete and added to the results list.

💡 Another leaf node adds a new valid permutation to the results.

Line:

if i == len(arr):
    res.append(''.join(arr))
    return

💡 All permutations are collected at the leaves of the recursion tree.

traverse

Backtrack to index 3: uppercase branch for 'b' (uppercase 'a' branch)

Backtracking to index 3, the algorithm sets 'b' to uppercase 'B' and recurses to index 4.

💡 Backtracking explores the uppercase branch for 'b' after lowercase is done.

Line:

arr[i] = arr[i].upper()
backtrack(i + 1)

💡 Backtracking systematically explores all letter case permutations.

reconstruct

Base case reached: add 'A1B2' to results

At index 4, the permutation 'A1B2' is complete and added to the results list.

💡 The final leaf node adds the last valid permutation to the results.

Line:

if i == len(arr):
    res.append(''.join(arr))
    return

💡 All permutations have now been collected in the results list.

backtracking

Backtrack to index 0: revert 'a' to original and finish

Backtracking reverts 'a' to original and completes all recursive calls. The final results list contains all permutations.

💡 Reverting the first character cleans up the state and ends recursion.

Line:

arr[i] = s[i]  # revert to original
return

💡 Backtracking ensures the original input is restored after exploring all branches.

from typing import List

def letterCasePermutation(s: str) -> List[str]:
    res = []  # STEP 1: initialize results
    arr = list(s)  # STEP 1: convert string to array
    def backtrack(i: int):
        if i == len(arr):  # STEP 6,8,13,15: base case
            res.append(''.join(arr))
            return
        if arr[i].isdigit():  # STEP 3,5,10,12: digit skip
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()  # STEP 2,4,11: lowercase branch
            backtrack(i + 1)
            arr[i] = arr[i].upper()  # STEP 7,14: uppercase branch
            backtrack(i + 1)
            arr[i] = s[i]  # STEP 9,16: revert
    backtrack(0)  # STEP 1: start recursion
    return res

if __name__ == '__main__':
    print(letterCasePermutation("a1b2"))

📊

Letter Case Permutation - Watch the Algorithm Execute, Step by Step

Watching this step-by-step recursion tree is the fastest way to understand how backtracking explores all letter case combinations systematically and how the algorithm reverts changes to explore alternative paths.

enteringi=0

Call Path (current → root)

backtrack(0)

Remaining

lowercase or uppercase for 'a'

enteringi=1

Call Path (current → root)

backtrack(1)

backtrack(0)

Remaining

digit skip at index 1

Partial: [a]

enteringi=2

Call Path (current → root)

backtrack(2)

backtrack(1)

backtrack(0)

Remaining

lowercase or uppercase for 'b'

Partial: [a, 1]

enteringi=3

Call Path (current → root)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Remaining

digit skip at index 3

Partial: [a, 1, b]

enteringi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Partial: [a, 1, b, 2]

backtrackingi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Partial: [a, 1, b, 2]

Found 1: [a1b2]

enteringi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Tried

lowercase

Remaining

uppercase

Partial: [a, 1, B, 2]

Found 1: [a1b2]

backtrackingi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Tried

lowercaseuppercase

Partial: [a, 1, B, 2]

Found 2: [a1b2] [a1B2]

enteringi=1

Call Path (current → root)

backtrack(1)

backtrack(0)

Tried

lowercase

Remaining

uppercase

Partial: [A]

Found 2: [a1b2] [a1B2]

enteringi=2

Call Path (current → root)

backtrack(2)

backtrack(1)

backtrack(0)

Remaining

lowercase or uppercase for 'b'

Partial: [A, 1]

Found 2: [a1b2] [a1B2]

enteringi=3

Call Path (current → root)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Remaining

digit skip at index 3

Partial: [A, 1, b]

Found 2: [a1b2] [a1B2]

enteringi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Partial: [A, 1, b, 2]

Found 2: [a1b2] [a1B2]

backtrackingi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Partial: [A, 1, b, 2]

Found 3: [a1B2] [A1b2]

enteringi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Tried

lowercase

Remaining

uppercase

Partial: [A, 1, B, 2]

Found 3: [a1B2] [A1b2]

backtrackingi=4

Call Path (current → root)

backtrack(4)

backtrack(3)

backtrack(2)

backtrack(1)

backtrack(0)

Tried

lowercaseuppercase

Partial: [A, 1, B, 2]

Found 4: [A1b2] [A1B2]

backtrackingi=0

Call Path (current → root)

backtrack(0)

Tried

lowercaseuppercase

Found 4: [A1b2] [A1B2]

Key Takeaways

✓ Backtracking explores all letter case permutations by branching at each letter and skipping digits.

This insight is hard to see from code alone because the recursion and branching are implicit; visualization makes the branching explicit.

✓ Digits do not increase the recursion tree's branching factor and are efficiently skipped.

Understanding how digits simplify the recursion helps grasp the algorithm's efficiency.

✓ Backtracking reverts changes to explore alternative branches cleanly, ensuring all permutations are generated without corrupting state.

The importance of reverting state is subtle in code but critical for correctness; visualization shows this clearly.

Practice

1. Consider the following Python code implementing combination sum with reuse allowed:

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)
    backtrack(0, [], target)
    return result

print(combinationSum([2,3,6,7], 7))

What is the exact output of this code?

easy

A. [[7]]

B. [[2, 2, 3], [7]]

C. [[2, 2, 3]]

D. [[7], [2, 2, 3]]

Solution

1. Step 1: Trace backtrack calls for candidates=[2,3,6,7], target=7

   Sorted candidates: [2,3,6,7]. The function tries counts of 2 from 0 to 3 (max_use=3), then recurses on next index. Valid combinations found are [7] and [2,2,3].

2. Step 2: Check order of results appended

   Backtracking explores index 0 with counts 0..3, then index 1, so [7] is found after [2,2,3]. The result list appends [7] first, then [2,2,3]. But since the code appends when target==0, the order is [[7], [2, 2, 3]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected combinations with correct order [OK]

Hint: Order depends on recursion path, not sorted output [OK]

Common Mistakes:

• Assuming output is sorted by combination length or lex order
• Missing one valid combination

2. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

3. Consider the following Python code that generates all subsets of nums = [1, 2, 3]. What is the value of subset when mask = 5 during the iteration?

easy

A. [1, 3]

B. [2, 3]

C. [1, 2]

D. [3]

Solution

1. Step 1: Convert mask=5 to binary

   5 in binary is 101, meaning bits 0 and 2 are set.

2. Step 2: Map bits to indices in nums

   Bit 0 corresponds to nums[0]=1, bit 2 corresponds to nums[2]=3, so subset = [1, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mask 5 selects elements at positions 0 and 2 -> [1, 3] [OK]

Hint: Mask bits correspond to included elements [OK]

Common Mistakes:

• Off-by-one bit indexing
• Confusing mask bits with element values

4. What is the time complexity of the optimal iterative approach for generating all unique subsets from an array of length n that may contain duplicates?

medium

A. O(n^2) because of nested loops over the array

B. O(2^n) since each element doubles the subsets

C. O(2^n * n) due to generating all subsets and copying them

D. O(n * 2^n) because sorting dominates the complexity

Solution

1. Step 1: Identify main operations affecting complexity

   Sorting takes O(n log n), which is dominated by subset generation. The algorithm generates all subsets (2^n) and copies subsets of average length O(n).

2. Step 2: Calculate total time complexity

   Generating all subsets is O(2^n), and copying each subset of length up to n leads to O(2^n * n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Copying subsets causes the extra factor n, not just 2^n [OK]

Hint: Copying subsets adds factor n to 2^n subsets [OK]

Common Mistakes:

• Ignoring subset copying cost and saying O(2^n)
• Confusing sorting cost as dominant
• Mistaking nested loops as O(n^2)

5. Suppose the problem changes: now candidates can include negative numbers, and you still want all unique combinations summing to the target with reuse allowed. Which modification to the backtracking approach is necessary to handle this variant correctly?

hard

A. Remove pruning on target < 0 and add a visited set to detect cycles to avoid infinite recursion.

B. No change needed; the existing backtracking with pruning on target < 0 still works correctly.

C. Sort candidates in descending order and prune when target is less than the smallest candidate.

D. Use dynamic programming instead of backtracking because negative numbers break recursion.

Solution

1. Step 1: Understand impact of negative candidates

   Negative numbers allow sums to decrease indefinitely, causing infinite recursion if pruning on target < 0 is used or missing.

2. Step 2: Modify pruning and cycle detection

   Pruning on target < 0 is invalid because target can oscillate; must remove it and add a visited set or memoization to detect repeated states and avoid infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection is essential when negative numbers allow infinite recursion [OK]

Hint: Negative numbers require cycle detection to prevent infinite recursion [OK]

Common Mistakes:

• Assuming pruning on target < 0 always applies
• Ignoring infinite recursion caused by negatives