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. You are given an array of integers and need to find an index where the sum of elements to the left equals the sum of elements to the right. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Maintain a running left sum and use the total sum to check the right sum in a single pass.

B. Use dynamic programming to store prefix sums and then binary search for the pivot index.

C. Use a brute force nested loop to compute left and right sums for each index.

D. Sort the array and use two pointers to find the pivot index.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding an index where left sum equals right sum efficiently.

2. Step 2: Identify the optimal approach

   Maintaining a running left sum and using the total sum to compute right sum on the fly allows a single pass with O(1) extra space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with running sums is O(n) time and O(1) space [OK]

Hint: Running left sum + total sum enables single pass [OK]

Common Mistakes:

• Assuming nested loops are necessary
• Thinking sorting helps with sums
• Confusing prefix sums with binary search

2. You are given a binary array and need to find the length of the longest contiguous subarray where the number of 0s and 1s are equal. Which approach guarantees an optimal O(n) time solution?

easy

A. Use a brute force nested loop to check all subarrays and count zeros and ones.

B. Use a greedy approach to expand the subarray whenever zeros and ones are balanced.

C. Use dynamic programming to store counts of zeros and ones for all subarrays.

D. Use prefix sums with a hash map to track the first occurrence of each prefix sum value.

Solution

1. Step 1: Understand the problem requires tracking balance of zeros and ones.

   Transform zeros to -1 and compute prefix sums to detect subarrays with sum zero.

2. Step 2: Use a hash map to store the earliest index of each prefix sum.

   This allows O(n) time detection of longest balanced subarray by checking if prefix sum repeats.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Brute force is O(n²), greedy and DP do not guarantee O(n) [OK]

Hint: Prefix sums + hash map track balance in O(n) [OK]

Common Mistakes:

• Thinking greedy can find longest balanced subarray
• Using DP without prefix sums
• Assuming brute force is optimal

3. The following code attempts to solve the Continuous Subarray Sum problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: updating remainder_map[running_sum] = i before checking condition

B. Line 11: verifying subarray length > 1

C. Line 9: checking if running_sum in remainder_map

D. Line 3: initializing running_sum to 0

Solution

1. Step 1: Understand remainder_map update timing

   The original code updated remainder_map[running_sum] = i before checking if running_sum already exists, overwriting the earliest index.

2. Step 2: Identify consequence of overwriting

   Overwriting earliest index causes missing longer subarrays that satisfy the condition, leading to false negatives.

3. Step 3: Correct the code

   Update remainder_map[running_sum] = i only if running_sum is not already in remainder_map, preserving earliest occurrence.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct code inserts remainder only if not present to preserve earliest index [OK]

Hint: Earliest remainder index must be preserved to find valid subarrays [OK]

Common Mistakes:

• Updating remainder map on every occurrence
• Not checking subarray length >= 2
• Modulo by zero errors

4. Suppose the problem is modified so that elements can be removed multiple times (i.e., you can reuse elements from the ends infinitely) to reduce x to zero. Which approach correctly adapts to this variant?

hard

A. Use a dynamic programming approach to find the minimum number of removals with unlimited reuse, similar to coin change.

B. Apply a greedy approach removing the largest elements repeatedly from ends until x is zero.

C. Use the same sliding window approach on the original array once; it still works without changes.

D. Use prefix and suffix sums with a hash map but ignore overlapping since reuse is allowed.

Solution

1. Step 1: Understand the reuse variant

   Since elements can be reused infinitely, the problem becomes similar to coin change where you want minimum coins (elements) summing to x.

2. Step 2: Recognize sliding window limitation

   Sliding window relies on contiguous subarrays without reuse; it cannot handle infinite reuse.

3. Step 3: Use DP approach

   Dynamic programming can find minimum removals with unlimited reuse by building solutions for all sums up to x.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles reuse, sliding window does not [OK]

Hint: Reuse implies DP coin change pattern [OK]

Common Mistakes:

• Assuming sliding window works with reuse
• Ignoring infinite reuse changes problem nature
• Using greedy which fails on some sums

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