Problem statement

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

Solution

Classical problem for sliding window (which can be seen as two pointers approach as well). Let us keep window and if it is possible, extend it to the right, if no, shrink it to the left.

  1. If we have 2 distinct elements in counter (variable dist) and new element is already inside or dist <= 1, then we need to extend it to the right. We check if we can do it, and if we have new element, increase dist, update ans.
  2. In opposite case, we need to remove one element from the left, do it, and if we completely removed this element, decrease dist.

Complexity

Time complexity is $\mathcal{O}(n)$, because in total we have $2n$ movements of our pointers. Space complexity is $\mathcal{O}(1)$.

Code

class Solution:
    def lengthOfLongestSubstringTwoDistinct(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