Longest Substring with At Most 2 Distinct

📋

Problem

Imagine you are analyzing a stream of characters from a user's typing pattern and want to find the longest segment where the user only used at most two different characters. This helps in understanding typing habits or detecting patterns.

Given a string s, find the length of the longest substring that contains at most two distinct characters. Input: A string s consisting of lowercase and/or uppercase English letters. Output: An integer representing the length of the longest substring with at most two distinct characters.

1 ≤ length of s ≤ 10^5s consists of English letters (both lowercase and uppercase)

Edge cases: Empty string → 0String with all identical characters → length of stringString with all distinct characters → 2

</>

IDE

def length_of_longest_substring_two_distinct(s: str) -> int:public int lengthOfLongestSubstringTwoDistinct(String s)int lengthOfLongestSubstringTwoDistinct(string s)function lengthOfLongestSubstringTwoDistinct(s)

def length_of_longest_substring_two_distinct(s: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int lengthOfLongestSubstringTwoDistinct(string s) {
    // Write your solution here
    return 0;
}

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

Common Bugs to Avoid

Wrong: Length larger than actual max substringNot shrinking window when distinct chars exceed 2, causing overcount.✅ Add logic to shrink window from left and update frequency map when distinct chars > 2.

Wrong: 0 for non-empty stringNot handling empty or single character strings properly, missing base case.✅ Return 0 immediately if string is empty; initialize max length to 1 if string length ≥ 1.

Wrong: Off-by-one errors in max lengthIncorrect window boundaries or frequency updates when shrinking window.✅ Carefully update window start index and frequency counts when removing chars.

Wrong: TLE on large inputUsing brute force O(n^2) approach instead of O(n) sliding window.✅ Implement sliding window with frequency map to achieve O(n) time complexity.

Wrong: Incorrect length due to limiting character countsConfusing problem with 0/1 knapsack style constraints, limiting char counts incorrectly.✅ Only track distinct characters count, not individual character limits.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Watch out for greedy approaches that fail on repeating patterns.

Optimize your solution to linear time using sliding window technique.

t1_01basic

Input{"s":"eceba"}

Expected3

⏱ Performance - must finish in 2000ms

The longest substring with at most 2 distinct characters is "ece" which has length 3.

💡 Consider using a sliding window to track characters and their counts.

💡 Maintain a frequency map and shrink the window when distinct chars exceed 2.

💡 Update max length when window has at most 2 distinct characters.

Why it failed: Returned length too large or small due to not correctly tracking when to shrink window; fix by decrementing frequency and removing chars when count hits zero.

✓ Correctly tracks frequencies and window size for at most 2 distinct chars.

t1_02basic

Input{"s":"ccaabbb"}

Expected5

⏱ Performance - must finish in 2000ms

The longest substring with at most 2 distinct characters is "aabbb" which has length 5.

💡 Try expanding the window and counting distinct chars with a frequency map.

💡 Shrink the window from the left when distinct chars exceed 2.

💡 Keep track of max length during valid windows.

Why it failed: Incorrect max length due to not updating after shrinking window; fix by updating max length only when window has ≤ 2 distinct chars.

✓ Properly maintains window and updates max length for at most 2 distinct chars.

t2_01edge

Input{"s":""}

Expected0

⏱ Performance - must finish in 2000ms

Empty string has no substrings, so result is 0.

💡 Check if input string is empty before processing.

💡 Return 0 immediately if string length is zero.

💡 Avoid processing frequency map for empty input.

Why it failed: Fails on empty input by not returning 0; fix by adding a base case for empty string.

✓ Handles empty string input correctly.

t2_02edge

Input{"s":"a"}

Expected1

⏱ Performance - must finish in 2000ms

Single character string has longest substring length 1.

💡 Single character string always has max length 1.

💡 Frequency map will have one entry with count 1.

💡 No need to shrink window since distinct chars ≤ 2.

Why it failed: Fails single character input by returning 0 or more than 1; fix by initializing max length to at least 1 if string not empty.

✓ Correctly handles single character input.

t2_03edge

Input{"s":"abc"}

Expected2

⏱ Performance - must finish in 2000ms

All distinct characters, longest substring with ≤ 2 distinct chars is length 2 (e.g., "ab").

💡 When distinct chars exceed 2, shrink window from left.

💡 Max length will be at most 2 for all distinct chars.

💡 Check all substrings with 2 distinct chars.

Why it failed: Fails to shrink window properly when distinct chars > 2; fix by removing leftmost char and updating frequency map.

✓ Correctly limits substring to at most 2 distinct chars.

t2_04edge

Input{"s":"bbbbbb"}

Expected6

⏱ Performance - must finish in 2000ms

All identical characters, entire string is longest substring with ≤ 2 distinct chars.

💡 Frequency map will have only one character.

💡 Window can expand to entire string without shrinking.

💡 Max length equals string length.

Why it failed: Fails to handle all identical chars by shrinking unnecessarily; fix by checking distinct count before shrinking.

✓ Correctly handles all identical characters.

t3_01corner

Input{"s":"abcabcabc"}

Expected2

⏱ Performance - must finish in 2000ms

Greedy approach fails here; longest substring with ≤ 2 distinct chars is length 2 (e.g., "ab").

💡 Greedy approach picking first two chars and extending may fail.

💡 Use sliding window with frequency map to track distinct chars dynamically.

💡 Shrink window when distinct chars exceed 2 to find correct max length.

Why it failed: Greedy approach returns 3 or more by not shrinking window; fix by implementing sliding window with frequency map and shrinking when distinct chars > 2.

✓ Correctly handles greedy trap by dynamic window adjustment.

t3_02corner

Input{"s":"aabbccddeeff"}

Expected4

⏱ Performance - must finish in 2000ms

Tests off-by-one errors; longest substring with ≤ 2 distinct chars is length 4 (e.g., "aabb").

💡 Check window boundaries carefully when shrinking.

💡 Ensure frequency counts are updated correctly when removing chars.

💡 Update max length only when window is valid.

Why it failed: Off-by-one error causes max length to be off by 1; fix by carefully updating window start and frequency map when shrinking.

✓ Correctly handles off-by-one boundary conditions.

t3_03corner

Input{"s":"ababababab"}

Expected10

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and unbounded; here all chars are two distinct chars repeated, so entire string length 10.

💡 All characters are only two distinct chars repeated.

💡 Window can expand to entire string without shrinking.

💡 No limit on character count, only distinct chars count.

Why it failed: Mistakenly limits character counts or shrinks window unnecessarily; fix by only tracking distinct chars count, not individual char limits.

✓ Correctly handles repeated two distinct chars without shrinking.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000 tests O(n) sliding window solution performance within 2 seconds.

💡 Brute force O(n^2) will time out on large input.

💡 Use sliding window with frequency map for O(n) time.

💡 Avoid nested loops and recomputing frequencies repeatedly.

Why it failed: Brute force or inefficient approach causes TLE; fix by implementing O(n) sliding window with frequency map.

✓ Solution runs in O(n) time and passes performance test.

Practice

1. Consider the following code snippet for finding the longest subarray with equal number of 0s and 1s. What is the value of max_length after processing the input [0, 1, 0, 1]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace prefix sums and first_occurrence updates.

   For input [0,1,0,1], prefix sums are: -1, 0, -1, 0 with offset indexing.

2. Step 2: Update max_length when prefix sum repeats.

   At i=1, prefix_sum=0 repeats at index -1 -> length=2; at i=3, prefix_sum=0 repeats again -> length=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Longest balanced subarray is entire array length 4 [OK]

Hint: Prefix sum repeats indicate balanced subarray [OK]

Common Mistakes:

• Off-by-one in length calculation
• Confusing prefix sum indexing
• Ignoring initial prefix sum at -1

2. What is the time complexity of the optimal approach that counts subarrays with maximum bounded by left and right using the subtraction of two counts (countAtMost)?

medium

A. O(n) because it makes two linear passes over the array

B. O(n^2) because it checks all subarrays explicitly

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

D. O(n) with O(n) extra space to store intermediate counts

Solution

1. Step 1: Identify operations in countAtMost

   countAtMost iterates over the array once, updating counters in O(1) time per element.

2. Step 2: Analyze overall complexity

   numSubarrayBoundedMax calls countAtMost twice, each O(n), so total time is O(n). No sorting or nested loops involved.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans -> O(n) time, constant space [OK]

Hint: Two linear scans, no nested loops or sorting [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking extra space is O(n)

3. The following code attempts to implement summaryRanges but has a subtle bug. Which line contains the bug?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

medium

A. Line 7: The inner while loop condition misses the last element in some cases.

B. Line 4: Not checking if input list is empty causes crash on empty input.

C. Line 11: Updating start to end + 1 might skip elements if end is not updated correctly.

D. Line 9: Always appending 'start->end' even when start == end causes incorrect output for single elements.

Solution

1. Step 1: Identify output format issue

   When start == end, the code appends 'num->num' instead of just 'num', which is incorrect per problem spec.

2. Step 2: Confirm other lines are correct

   Inner loop condition and start update are correct; empty input handling is not shown but not the subtle bug here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single element ranges must be output as single numbers, not ranges [OK]

Hint: Single element ranges output as 'num', not 'num->num' [OK]

Common Mistakes:

• Appending 'start->end' even when start == end
• Off-by-one in inner loop
• Skipping last range due to loop condition

4. Suppose the problem is modified so that elements can be reused multiple times in the subsequence (i.e., indices can be repeated). Which modification to the DP approach correctly handles this variant?

hard

A. Use a recursive memoized solution that tries all possible next elements including the current one

B. Keep the same DP but allow j to equal i in the inner loop to reuse elements

C. Modify DP to track counts per difference but reset dp[i][diff] to 1 each time to allow reuse

D. Use a graph-based BFS to explore sequences allowing repeated nodes

Solution

1. Step 1: Understand reuse means indices can repeat

   Standard DP assumes strictly increasing indices; allowing reuse breaks this assumption.

2. Step 2: Recognize recursive memoization can explore all sequences with repeated elements

   Recursive approach with memoization can try all next elements including current, correctly handling reuse.

3. Step 3: Evaluate other options

   Allowing j == i breaks DP indexing logic; resetting dp[i][diff] loses subsequence length info; BFS is inefficient and complex.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recursive memoization handles repeated indices correctly [OK]

Hint: Reuse requires recursion with memoization, not standard DP indexing [OK]

Common Mistakes:

• Allowing j == i in DP loops breaks monotonic index assumption
• Resetting dp values loses subsequence length info
• Trying BFS which is inefficient

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