Longest Substring With At Most Two Distinct Characters - Leetcode Solution

Problem:

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: t is "ece" which contains 2 distinct characters 'e' and 'c'.

Example 2:

Input: "ccaabbb" Output: 5 Explanation: t is "aabbb" which contains 2 distinct characters 'a' and 'b'.

Solution:

To solve this problem, we can use a sliding window approach. We maintain a window of characters and keep track of the number of distinct characters in it. Once the window contains more than two distinct characters, we move the window's left boundary to shrink it until we have two distinct characters again. We keep track of the maximum length of the window seen so far.

Algorithm:

1. Initialize left and right pointers to the beginning of the string s.
2. Initialize a dictionary to keep track of the count of each character in the current window.
3. Initialize a variable max_len to zero to keep track of the length of the maximum substring.
4. Loop over the string s from left to right.
   • Increment the count of the current character in the dictionary.
   • If the number of distinct characters in the dictionary is greater than 2, decrement the count of the leftmost character in the dictionary and move the left pointer to the right until the number of distinct characters in the dictionary is back to 2.
   • Update the value of max_len if the length of the current window is greater than max_len.
5. Return max_len.

Code:

def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    left, right = 0, 0
    window = {}
    max_len = 0
    
    while right < len(s):
        if s[right] not in window:
            window[s[right]] = 0
        window[s[right]] += 1
        
        while len(window) > 2:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
            
        max_len = max(max_len, right - left + 1)
        right += 1
        
    return max_len

Time Complexity: O(n), where n is the length of the string s.

Space Complexity: O(1), since the dictionary has at most 3 elements.

1