Longest Substring with At Most Two Distinct Characters

Given a string s, return the length of the longest substring containing at most two distinct characters.

Note: You may assume that s only contains lowercase alphabetical characters.

Example(s)

Example 1:

Input: s = "aba"
Output: 3
Explanation:
The entire string "aba" contains at most 2 distinct characters ('a' and 'b').
Length = 3

Example 2:

Input: s = "abca"
Output: 2
Explanation:
Substrings with at most 2 distinct characters:
- "ab" (length 2)
- "bc" (length 2)
- "ca" (length 2)
Longest: 2
Note: "abca" has 3 distinct characters, so it doesn't qualify.

Example 3:

Input: s = "eceba"
Output: 3
Explanation:
The longest substring is "ece" (length 3) with characters 'e' and 'c'.

Example 4:

Input: s = "ccaabbb"
Output: 5
Explanation:
The longest substring is "aabbb" (length 5) with characters 'a' and 'b'.

Solution

The solution uses the sliding window technique:

1. Two pointers: Use left and right to define the window
2. Hash map: Track frequency of characters in the current window
3. Expand window: Move right pointer and add characters
4. Shrink window: If we have more than 2 distinct characters, move left until we have at most 2
5. Track maximum: Keep track of the maximum window size

JavaScript Solution

JavaScript Solution - Sliding Window

/**
* Find length of longest substring with at most 2 distinct characters
* @param {string} s - Input string
* @return {number} - Length of longest substring
*/
function lengthOfLongestSubstringTwoDistinct(s) {
if (!s || s.length === 0) return 0;

const charCount = new Map();
let left = 0;
let maxLength = 0;

// Expand window with right pointer
for (let right = 0; right < s.length; right++) {
  // Add current character to window
  const char = s[right];
  charCount.set(char, (charCount.get(char) || 0) + 1);
  
  // Shrink window if we have more than 2 distinct characters
  while (charCount.size > 2) {
    const leftChar = s[left];
    const count = charCount.get(leftChar);
    
    if (count === 1) {
      charCount.delete(leftChar);
    } else {
      charCount.set(leftChar, count - 1);
    }
    
    left++;
  }
  
  // Update maximum length
  maxLength = Math.max(maxLength, right - left + 1);
}

return maxLength;
}

// Test cases
console.log('Example 1:', lengthOfLongestSubstringTwoDistinct("aba")); // 3
console.log('Example 2:', lengthOfLongestSubstringTwoDistinct("abca")); // 2
console.log('Example 3:', lengthOfLongestSubstringTwoDistinct("eceba")); // 3
console.log('Example 4:', lengthOfLongestSubstringTwoDistinct("ccaabbb")); // 5
console.log('Test 5:', lengthOfLongestSubstringTwoDistinct("a")); // 1
console.log('Test 6:', lengthOfLongestSubstringTwoDistinct("abcabcabc")); // 2

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Sliding Window

from typing import Dict
from collections import defaultdict

def length_of_longest_substring_two_distinct(s: str) -> int:
  """
  Find length of longest substring with at most 2 distinct characters
  
  Args:
      s: Input string
      
  Returns:
      int: Length of longest substring
  """
  if not s:
      return 0
  
  char_count: Dict[str, int] = defaultdict(int)
  left = 0
  max_length = 0
  
  # Expand window with right pointer
  for right in range(len(s)):
      # Add current character to window
      char = s[right]
      char_count[char] += 1
      
      # Shrink window if we have more than 2 distinct characters
      while len(char_count) > 2:
          left_char = s[left]
          char_count[left_char] -= 1
          
          if char_count[left_char] == 0:
              del char_count[left_char]
          
          left += 1
      
      # Update maximum length
      max_length = max(max_length, right - left + 1)
  
  return max_length

# Test cases
print('Example 1:', length_of_longest_substring_two_distinct("aba"))  # 3
print('Example 2:', length_of_longest_substring_two_distinct("abca"))  # 2
print('Example 3:', length_of_longest_substring_two_distinct("eceba"))  # 3
print('Example 4:', length_of_longest_substring_two_distinct("ccaabbb"))  # 5
print('Test 5:', length_of_longest_substring_two_distinct("a"))  # 1
print('Test 6:', length_of_longest_substring_two_distinct("abcabcabc"))  # 2

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (More Explicit)

Here's a more explicit version that might be easier to understand:

JavaScript Alternative

/**
 * More explicit version
 */
function lengthOfLongestSubstringTwoDistinctExplicit(s) {
  if (!s) return 0;
  
  const charMap = new Map();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const rightChar = s[right];
    charMap.set(rightChar, (charMap.get(rightChar) || 0) + 1);
    
    // If we have more than 2 distinct characters, shrink window
    if (charMap.size > 2) {
      // Move left pointer until we have at most 2 distinct characters
      while (charMap.size > 2) {
        const leftChar = s[left];
        const count = charMap.get(leftChar);
        
        if (count === 1) {
          charMap.delete(leftChar);
        } else {
          charMap.set(leftChar, count - 1);
        }
        
        left++;
      }
    }
    
    // Update maximum
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Python Alternative

def length_of_longest_substring_two_distinct_explicit(s: str) -> int:
    """
    More explicit version
    """
    if not s:
        return 0
    
    char_map = {}
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        right_char = s[right]
        char_map[right_char] = char_map.get(right_char, 0) + 1
        
        # If we have more than 2 distinct characters, shrink window
        if len(char_map) > 2:
            # Move left pointer until we have at most 2 distinct characters
            while len(char_map) > 2:
                left_char = s[left]
                char_map[left_char] -= 1
                
                if char_map[left_char] == 0:
                    del char_map[left_char]
                
                left += 1
        
        # Update maximum
        max_len = max(max_len, right - left + 1)
    
    return max_len

Complexity

• Time Complexity: O(n) - Where n is the length of the string. Each character is visited at most twice (once by right pointer, once by left pointer).
• Space Complexity: O(1) - The hash map stores at most 3 entries (2 distinct characters + 1 temporary during shrinking), so it's O(1).

Approach

The solution uses the sliding window technique:

1. Two pointers:

   • left: Start of the current window
   • right: End of the current window (expanding)

2. Hash map:

   • Track frequency of each character in the current window
   • When charCount.size > 2, we have too many distinct characters

3. Expand window:

   • Move right pointer forward
   • Add character to the map

4. Shrink window:

   • If we have more than 2 distinct characters, move left pointer
   • Remove characters from map until we have at most 2 distinct characters

5. Track maximum:

   • Update maximum window size after each expansion

Key Insights

• Sliding window: Maintain a window with at most 2 distinct characters
• Two pointers: Left and right pointers define the window
• Hash map: Efficiently track character frequencies
• Shrink when needed: When we exceed 2 distinct characters, shrink from left
• O(n) time: Each character visited at most twice

Step-by-Step Example

Let's trace through Example 2: s = "abca"

Initial: left = 0, right = 0, charCount = {}, maxLength = 0

right = 0: s[0] = 'a'
  charCount = {'a': 1}
  charCount.size = 1 <= 2 ✓
  maxLength = max(0, 0-0+1) = 1

right = 1: s[1] = 'b'
  charCount = {'a': 1, 'b': 1}
  charCount.size = 2 <= 2 ✓
  maxLength = max(1, 1-0+1) = 2

right = 2: s[2] = 'c'
  charCount = {'a': 1, 'b': 1, 'c': 1}
  charCount.size = 3 > 2 ✗
  Shrink window:
    left = 0: s[0] = 'a', count = 1
    Remove 'a': charCount = {'b': 1, 'c': 1}
    left = 1
  charCount.size = 2 <= 2 ✓
  maxLength = max(2, 2-1+1) = 2

right = 3: s[3] = 'a'
  charCount = {'b': 1, 'c': 1, 'a': 1}
  charCount.size = 3 > 2 ✗
  Shrink window:
    left = 1: s[1] = 'b', count = 1
    Remove 'b': charCount = {'c': 1, 'a': 1}
    left = 2
  charCount.size = 2 <= 2 ✓
  maxLength = max(2, 3-2+1) = 2

Final: maxLength = 2

Visual Representation

Example 2: s = "abca"

Window expansion:
a          → distinct: 1, length: 1
ab         → distinct: 2, length: 2 ✓
 bc        → distinct: 2, length: 2 ✓
  ca       → distinct: 2, length: 2 ✓

Maximum: 2

Edge Cases

• Empty string: Return 0
• Single character: Return 1
• All same character: Return string length
• Exactly 2 distinct: Return string length
• More than 2 distinct: Find longest substring with 2 distinct

Important Notes

• At most 2: Can have 1 or 2 distinct characters
• Substring: Must be contiguous
• Sliding window: Efficiently maintains valid window
• Hash map size: At most 3 entries (during shrinking)
• O(1) space: Since we only track at most 3 characters

Related Problems

• Longest Substring Without Repeating Characters: Similar sliding window
• Longest Substring with At Most K Distinct Characters: Generalization (k=2)
• Minimum Window Substring: Different constraint
• Longest Repeating Character Replacement: Different problem

Takeaways

• Sliding window is the key technique for substring problems
• Two pointers efficiently maintain a valid window
• Hash map tracks character frequencies
• Shrink when invalid maintains window validity
• O(n) time is optimal (each character visited at most twice)