LeetCode 159. Longest Substring with At Most Two Distinct Characters

Description

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

Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: tis "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.

Explanation

Two pointers. Keep faster pointer moving to the right until more than 2 distinct characters. Then adjust slower pointer and repeat the same.

Python Solution

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        if not s:
            return ""
        
        
        max_length = 1
        j = 0
        counter = {}
        
        for i in range(len(s)):
            while j < len(s) and (len(counter) < 2 or (len(counter) == 2 and s[j] in counter)):
                counter[s[j]] = counter.get(s[j], 0) + 1
                j += 1
                
            if len(counter) <= 2:
                max_length = max(max_length, j - i)
                
            counter[s[i]] -= 1
            
            if counter[s[i]] == 0:
                del counter[s[i]]
                
                
        return max_length
            

• Time Complexity: ~N
• Space Complexity: ~1

where N is a number of characters in the input string.