Longest Substring with At Most Two Distinct Characters [Hard]

Problem Statement

Given string s, find the length of the longest substring with at most two distinct characters.

Input: "eceba" → Output: 3 ("ece")
Input: "ccaabbb" → Output: 5 ("aabbb")

Intuition

Variable sliding window tracking at most 2 distinct chars in a HashMap. When 3rd char enters, shrink from left.

Solutions

C++

int lengthOfLongestSubstringTwoDistinct(string s) {
    unordered_map<char,int> cnt;
    int left=0, ans=0;
    for(int r=0;r<s.size();r++){
        cnt[s[r]]++;
        while(cnt.size()>2){if(--cnt[s[left]]==0)cnt.erase(s[left]);left++;}
        ans=max(ans,r-left+1);
    }
    return ans;
}

Java

public int lengthOfLongestSubstringTwoDistinct(String s) {
    Map<Character,Integer> cnt=new HashMap<>();
    int left=0, ans=0;
    for(int r=0;r<s.length();r++){
        cnt.merge(s.charAt(r),1,Integer::sum);
        while(cnt.size()>2){
            char c=s.charAt(left++);
            cnt.merge(c,-1,Integer::sum);
            if(cnt.get(c)==0) cnt.remove(c);
        }
        ans=Math.max(ans,r-left+1);
    }
    return ans;
}

Python

from collections import defaultdict

def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    cnt = defaultdict(int)
    left = ans = 0
    for right, c in enumerate(s):
        cnt[c] += 1
        while len(cnt) > 2:
            cnt[s[left]] -= 1
            if cnt[s[left]] == 0: del cnt[s[left]]
            left += 1
        ans = max(ans, right - left + 1)
    return ans

Complexity

Time: O(n), Space: O(1) — at most 3 entries in map