Longest Substring with At Most 2 Distinct

▶

Steps

setup

Initialize frequency array and pointers

Initialize a frequency array of size 128 with zeros, set left pointer to 0, max_length to 0, and distinct_count to 0 before starting the iteration.

💡 This setup prepares the data structures and variables needed to track character frequencies and window boundaries.

Line:

freq = [0] * 128
left = 0
max_length = 0
distinct_count = 0

💡 The algorithm starts with an empty window and no characters counted.

fill_cells

Expand right pointer to 'e' at index 0

Right pointer moves to index 0, character 'e'. Since 'e' frequency is 0, distinct_count increments to 1. Frequency of 'e' is incremented to 1.

💡 Adding the first character starts building the window and tracking distinct characters.

Line:

if freq[ord(s[right])] == 0:
    distinct_count += 1
freq[ord(s[right])] += 1

💡 The window now contains one distinct character 'e' with frequency 1.

update

Update max_length after including 'e'

Calculate current window size (right - left + 1 = 1) and update max_length to 1 since it's larger than previous max_length 0.

💡 Tracking max_length ensures we remember the longest valid substring found so far.

Line:

max_length = max(max_length, right - left + 1)

💡 The longest substring with at most 2 distinct characters so far is 'e' with length 1.

fill_cells

Expand right pointer to 'c' at index 1

Right pointer moves to index 1, character 'c'. Since 'c' frequency is 0, distinct_count increments to 2. Frequency of 'c' is incremented to 1.

💡 Adding a second distinct character expands the window while still meeting the constraint.

Line:

if freq[ord(s[right])] == 0:
    distinct_count += 1
freq[ord(s[right])] += 1

💡 The window now contains two distinct characters 'e' and 'c', each with frequency 1.

update

Update max_length after including 'c'

Calculate current window size (right - left + 1 = 2) and update max_length to 2 since it's larger than previous max_length 1.

💡 The window size increases as we add valid characters, updating max_length accordingly.

Line:

max_length = max(max_length, right - left + 1)

💡 The longest substring with at most 2 distinct characters so far is 'ec' with length 2.

fill_cells

Expand right pointer to 'e' at index 2

Right pointer moves to index 2, character 'e'. Since 'e' frequency is 1 (already in window), distinct_count remains 2. Frequency of 'e' increments to 2.

💡 Adding an existing character increases its frequency without increasing distinct_count.

Line:

if freq[ord(s[right])] == 0:
    distinct_count += 1
freq[ord(s[right])] += 1

💡 The window now has 'e' with frequency 2 and 'c' with frequency 1, still within the 2 distinct character limit.

update

Update max_length after including second 'e'

Calculate current window size (right - left + 1 = 3) and update max_length to 3 since it's larger than previous max_length 2.

💡 The window size increases as repeated characters are added, updating max_length.

Line:

max_length = max(max_length, right - left + 1)

💡 The longest substring with at most 2 distinct characters so far is 'ece' with length 3.

fill_cells

Expand right pointer to 'b' at index 3

Right pointer moves to index 3, character 'b'. Since 'b' frequency is 0, distinct_count increments to 3, exceeding the allowed 2 distinct characters. Frequency of 'b' increments to 1.

💡 Adding a third distinct character violates the constraint, triggering window contraction.

Line:

if freq[ord(s[right])] == 0:
    distinct_count += 1
freq[ord(s[right])] += 1

💡 The window now contains three distinct characters: 'e', 'c', and 'b'.

shrink

Shrink window from left to remove 'e' at index 0

Left pointer moves from index 0 to 1. Frequency of 'e' decremented from 2 to 1. distinct_count remains 3 because 'e' frequency is still > 0.

💡 Shrinking the window reduces frequencies to restore the constraint of at most 2 distinct characters.

Line:

freq[ord(s[left])] -= 1
if freq[ord(s[left])] == 0:
    distinct_count -= 1
left += 1

💡 The window shrinks but still contains 3 distinct characters, so shrinking continues.

shrink

Shrink window from left to remove 'c' at index 1

Left pointer moves from index 1 to 2. Frequency of 'c' decremented from 1 to 0. distinct_count decremented to 2 because 'c' frequency reached 0.

💡 Removing a character completely from the window reduces distinct_count, restoring the constraint.

Line:

freq[ord(s[left])] -= 1
if freq[ord(s[left])] == 0:
    distinct_count -= 1
left += 1

💡 The window now contains only two distinct characters: 'e' and 'b'.

update

Update max_length after shrinking window

Calculate current window size (right - left + 1 = 2) and max_length remains 3 since 2 < 3.

💡 Max_length only updates if the current window is longer than previous max_length.

Line:

max_length = max(max_length, right - left + 1)

💡 The longest substring remains 'ece' with length 3.

fill_cells

Expand right pointer to 'a' at index 4

Right pointer moves to index 4, character 'a'. Since 'a' frequency is 0, distinct_count increments to 3 again. Frequency of 'a' increments to 1.

💡 Adding a new distinct character again violates the constraint, requiring further shrinking.

Line:

if freq[ord(s[right])] == 0:
    distinct_count += 1
freq[ord(s[right])] += 1

💡 The window now contains 'e', 'b', and 'a' with frequencies 1,1,1 respectively.

shrink

Shrink window from left to remove 'e' at index 2

Left pointer moves from index 2 to 3. Frequency of 'e' decremented from 1 to 0. distinct_count decremented to 2 because 'e' frequency reached 0.

💡 Removing 'e' restores the constraint of at most 2 distinct characters.

Line:

freq[ord(s[left])] -= 1
if freq[ord(s[left])] == 0:
    distinct_count -= 1
left += 1

💡 The window now contains 'b' and 'a' only.

update

Update max_length after final window adjustment

Calculate current window size (right - left + 1 = 2) and max_length remains 3 since 2 < 3.

💡 Max_length preserves the longest valid substring length found during the entire process.

Line:

max_length = max(max_length, right - left + 1)

💡 The longest substring with at most 2 distinct characters is 'ece' with length 3.

reconstruct

Return the final max_length

After processing all characters, return max_length which is 3, the length of the longest substring with at most 2 distinct characters.

💡 Returning the final result completes the algorithm.

Line:

return max_length

💡 The answer is the maximum window size found during the iteration.

def length_of_longest_substring_two_distinct(s: str) -> int:
    freq = [0] * 128  # STEP 1
    left = 0  # STEP 1
    max_length = 0  # STEP 1
    distinct_count = 0  # STEP 1
    for right in range(len(s)):  # STEP 2 to 14
        if freq[ord(s[right])] == 0:  # STEP 2,4,6,8,12
            distinct_count += 1  # STEP 2,4,6,8,12
        freq[ord(s[right])] += 1  # STEP 2,4,6,8,12
        while distinct_count > 2:  # STEP 8,9,10,13
            freq[ord(s[left])] -= 1  # STEP 9,10,13
            if freq[ord(s[left])] == 0:  # STEP 10,13
                distinct_count -= 1  # STEP 10,13
            left += 1  # STEP 9,10,13
        max_length = max(max_length, right - left + 1)  # STEP 3,5,7,11,14
    return max_length  # STEP 15

if __name__ == '__main__':
    test_str = "eceba"
    print(length_of_longest_substring_two_distinct(test_str))  # Expected output: 3

📊

Longest Substring with At Most 2 Distinct - Watch the Algorithm Execute, Step by Step

Watching each frequency update and pointer movement reveals how the algorithm efficiently manages the substring constraints without re-scanning the string.

insert

empty map

Result: 0

insert

Lookup: e→ 0

e→1lookup

Result: 0

check

e→1

Result: 1

insert

Lookup: c→ 0

e→1

c→1lookup

Result: 1

check

e→1

c→1

Result: 2

increment

Lookup: e→ 1

e→2lookup

c→1

Result: 2

check

e→2

c→1

Result: 3

insert

Lookup: b→ 0

e→2

c→1

b→1lookup

Result: 3

decrement

Lookup: e→ 2

e→1lookup

c→1

b→1

Result: 3

delete

Lookup: c→ 1

e→1

c→0lookup

b→1

Result: 3

check

e→1

c→0

b→1

Result: 3

insert

Lookup: a→ 0

e→1

b→1

a→1lookup

c→0

Result: 3

delete

Lookup: e→ 1

e→0lookup

b→1

a→1

c→0

Result: 3

check

e→0

b→1

a→1

c→0

Result: 3

check

b→1

a→1

Result: 3

Key Takeaways

✓ Tracking character frequencies with a hash map allows efficient detection of when the window exceeds the allowed distinct characters.

This insight is hard to see from code alone because frequency updates and distinct count changes happen implicitly and can be confusing without visualization.

✓ The sliding window expands by moving the right pointer and contracts by moving the left pointer to maintain the constraint.

Visualizing each pointer movement clarifies how the window adjusts dynamically rather than scanning the string multiple times.

✓ Max_length updates only when the current window size is larger, preserving the longest valid substring found so far.

Understanding when and why max_length updates helps connect the algorithm's goal to the frequency tracking and window adjustments.

Practice

1. Given the following code and input nums = [3,1,1,1,5], x = 5, what is the returned value?

easy

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate totalSum and target

   totalSum = 3+1+1+1+5 = 11; target = 11 - 5 = 6.

2. Step 2: Use sliding window to find longest subarray summing to 6

   Window expands: [3] sum=3, [3,1] sum=4, [3,1,1] sum=5, [3,1,1,1] sum=6 -> max_len=4; next, add 5 sum=11 > 6, shrink from left: remove 3 sum=8 >6, remove 1 sum=7 >6, remove 1 sum=6 -> max_len=4 remains (subarray [1,1,1]).

3. Step 3: Calculate minimum operations

   Minimum removals = array length - max_len = 5 - 4 = 1.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Longest subarray length 4 -> min ops = 1 [OK]

Hint: Sliding window finds longest subarray sum [OK]

Common Mistakes:

• Off-by-one errors in window length calculation
• Miscomputing sums when shrinking window
• Confusing min operations with longest subarray length

2. What is the time complexity of the optimal single-pass pivot index algorithm that uses a running left sum and total sum?

medium

A. O(n) because it iterates through the array once, updating sums in constant time.

B. O(n^2) because of nested sum computations inside the loop.

C. O(n log n) due to sorting the array before processing.

D. O(n) time but O(n) space due to storing prefix sums.

Solution

1. Step 1: Analyze loop iterations

   The algorithm iterates through the array once, performing constant time operations per element.

2. Step 2: Confirm no nested loops or extra space

   There are no nested loops or sorting; space used is O(1) for running sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant time per element -> O(n) [OK]

Hint: Single loop with constant work per iteration -> O(n) [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Forgetting space is O(1) not O(n)

3. Identify the bug in the following code snippet for the Minimum Operations to Reduce X to Zero problem:

medium

A. Line with 'if target == 0: return -1' should return len(nums) instead.

B. The while loop condition should be 'current_sum >= target' instead of '>'.

C. The initialization of max_len should be 0 instead of -1.

D. The final return should be 'max_len' instead of 'len(nums) - max_len'.

Solution

1. Step 1: Understand the edge case when target == 0

   If target == 0, it means totalSum == x, so removing all elements is needed, so minimum operations = length of array.

2. Step 2: Identify incorrect return value

   The code returns -1 incorrectly, which signals no solution, but the correct answer is to remove all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning -1 here causes wrong output on full removal case [OK]

Hint: Check edge cases where x equals total sum [OK]

Common Mistakes:

• Returning -1 instead of full length when target == 0
• Misinterpreting no solution vs full removal
• Ignoring edge cases in initial checks

4. Suppose the problem is modified so that characters in t can be reused unlimited times in the substring (i.e., the substring must contain at least one occurrence of each character in t, but counts do not matter). Which of the following algorithmic changes correctly adapts the sliding window approach?

hard

A. Keep frequency counts but ignore counts when checking if window is valid; only check presence of characters

B. No changes needed; the original frequency counting approach works as is

C. Use the original frequency map and formed count but reset formed to zero after each window

D. Use a set to track presence of required characters and expand/shrink window until all are present

Solution

1. Step 1: Understand problem change

   Now only presence of each character in t is required, not counts. So frequency counts are unnecessary; presence tracking suffices.

2. Step 2: Adapt algorithm

   Using a set to track which required characters are currently in the window allows efficient checking. Expand window until all required chars are present, then shrink to minimize.

3. Step 3: Why other options fail

   Ignoring counts but keeping frequency maps wastes time and complicates logic. Resetting formed to zero after each window breaks continuity. Original approach requires exact counts, so no changes is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Presence tracking with sets fits the relaxed requirement [OK]

Hint: Presence tracking replaces frequency counting [OK]

Common Mistakes:

• Ignoring that counts no longer matter
• Trying to reuse frequency counts unnecessarily

5. Suppose the input array can contain negative numbers and you want to find the number of subarrays whose sum equals k, but now you want to find the count of subarrays with sum divisible by k instead. Which modification to the optimal prefix sum with hash map approach correctly solves this variant?

hard

A. Use a sliding window approach since divisibility allows shrinking the window easily.

B. Track prefix sums modulo k and count frequencies of each remainder in a hash map.

C. Sort the array and use two pointers to find subarrays with sum divisible by k.

D. Use the original prefix sum approach without changes, as sum equals k and sum divisible by k are equivalent.

Solution

1. Step 1: Understand the problem variant

   We want subarrays where sum % k == 0, not sum == k.

2. Step 2: Modify prefix sums to track remainders

   Compute prefix sums modulo k and count how many prefix sums have the same remainder, since difference of prefix sums with same remainder is divisible by k.

3. Step 3: Use hash map to count frequencies of remainders

   Increment count by frequency of current remainder seen so far.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Sliding window fails with negatives; sorting breaks subarray continuity; original approach doesn't handle divisibility. [OK]

Hint: Use prefix sums modulo k and count remainder frequencies [OK]

Common Mistakes:

• Trying sliding window with negatives
• Ignoring modulo operation
• Assuming sum equals k and divisible by k are same