BinarySearch 0436 Longest Substring with 2 Distinct Characters

Problem statement

https://binarysearch.com/problems/Longest-Substring-with-2-Distinct-Characters/

Solution

Equal to Leetcode 0159 Longest Substring with At Most Two Distinct Characters.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, s):
        window = Counter()
        beg, end, ans, n, dist = 0, 0, 0, len(s), 0
        
        while beg < n and end < n:
            if (dist == 2 and window[s[end]] > 0) or dist <= 1:
                if end + 1 < n: window[s[end]] += 1
                if window[s[end]] == 1: dist += 1
                end += 1
                ans = max(ans, end - beg)
            else:
                window[s[beg]] -= 1
                if window[s[beg]] == 0: dist -= 1
                beg += 1
        
        return ans