{x}
blog image

Longest Substring with At Most Two Distinct Characters

Solution Explanation: Sliding Window Approach

This problem can be efficiently solved using a sliding window approach. The core idea is to maintain a window within the string s that contains at most two distinct characters. We expand the window as long as it satisfies this condition, and update the maximum length found so far. If the window contains more than two distinct characters, we shrink it from the left until the condition is met again.

Algorithm:

  1. Initialization: We use a hash map (dictionary in Python) cnt to store the frequency of each character within the current window. Two pointers, i (left) and j (right), define the window's boundaries. ans stores the maximum length found.

  2. Expansion: The right pointer j iterates through the string. For each character s[j], we increment its count in cnt.

  3. Contraction: If the number of distinct characters in cnt (using len(cnt) in Python, cnt.size() in Java/C++, or len(cnt) in Go) exceeds 2, we need to shrink the window. The left pointer i moves forward, decrementing the count of s[i] in cnt. If the count of s[i] becomes 0 after decrementing, we remove it from cnt. We repeat this contraction until cnt has at most two distinct characters.

  4. Update Maximum: After each expansion or contraction, we update ans with the maximum length of the current window (i - j + 1).

  5. Return: Finally, ans contains the length of the longest substring with at most two distinct characters.

Time Complexity: O(N), where N is the length of the string. Each character is visited and processed at most twice (once during expansion and once during contraction).

Space Complexity: O(1). The hash map cnt stores at most two distinct characters, so its space usage is constant regardless of the input string's size. (Technically, the space usage is O(min(N, 26)) as we may need to store all 26 characters in the worst case. However, we can assume the number of unique characters is limited in the problem setting, hence O(1)).

Code Explanation (Python):

from collections import Counter
 
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        cnt = Counter()  # Frequency counter for characters in the window
        ans = j = 0      # Initialize max length and right pointer
        for i, c in enumerate(s): # Efficient iteration using enumerate
            cnt[c] += 1       # Add the current character to the window
            while len(cnt) > 2: # Shrink the window if more than 2 distinct chars
                cnt[s[j]] -= 1 # Decrement the leftmost character's count
                if cnt[s[j]] == 0: #Remove from counter if count becomes zero
                    del cnt[s[j]]  
                j += 1           # Move left pointer
            ans = max(ans, i - j + 1) #Update the maximum length
        return ans

The other languages (Java, C++, Go) follow the same logic, adapting the syntax and data structures to each language. For example, in Java, HashMap is used instead of Counter, and cnt.size() replaces len(cnt). The core algorithm remains the same.