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 code snippet implementing the trie-based solution for counting valid words for puzzles. Given the words = ["apple", "plea", "plead"] and puzzles = ["aelwxyz"], what is the returned count for this puzzle?

easy

A. [1]

B. [0]

C. [2]

D. [3]

Solution

1. Step 1: Compute bitmasks for words

   "apple" -> letters {a,p,l,e}, mask with ≤7 bits; "plea" and "plead" similarly processed.

2. Step 2: Check puzzle "aelwxyz"

   First letter 'a' must be in word; words "apple" and "plea" contain 'a' and are subsets of puzzle letters; "plead" contains 'd' not in puzzle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two words match conditions [OK]

Hint: Count words containing puzzle first letter and subset of puzzle letters [OK]

Common Mistakes:

• Counting words missing first letter
• Including words with letters outside puzzle
• Off-by-one in counting matches

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. 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 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

5. Suppose the problem is modified so that each element in the array can be used multiple times to form the k equal sum subsets (i.e., unlimited reuse of elements). Which modification to the backtracking with bitmask memoization approach is necessary to correctly solve this variant?

hard

A. Keep bitmask but allow resetting bits after each recursive call

B. Sort ascending instead of descending to handle reuse properly

C. Use the same code without changes because bitmask handles reuse implicitly

D. Remove bitmask usage since elements can be reused; track counts instead

Solution

1. Step 1: Understand reuse impact on state representation

   Bitmask tracks used elements uniquely; with reuse allowed, usage state is not binary but counts.

2. Step 2: Modify approach accordingly

   Bitmask must be removed or replaced by frequency counts to track how many times each element is used; otherwise, states are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask cannot represent multiple uses of same element [OK]

Hint: Bitmask tracks usage once; reuse breaks this assumption [OK]

Common Mistakes:

• Trying to reuse bitmask for multiple uses
• Ignoring state representation changes