To solve this problem, we need to find the length of the longest substring in a given string that contains at most two distinct characters. This problem can be efficiently solved using the sliding window technique, which allows us to maintain a window of characters and adjust its size based on the number of distinct characters present.

Approach

1. Sliding Window Technique: We use two pointers (left and right) to represent the current window of characters being considered.
2. Frequency Map: A frequency dictionary is used to keep track of the count of each character in the current window.
3. Adjust Window: If the number of distinct characters in the window exceeds two, we shrink the window from the left until the number of distinct characters is at most two.
4. Max Length Calculation: For each valid window (with at most two distinct characters), we update the maximum length of the window.

Solution Code

from collections import defaultdict

def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    if len(s) <= 2:
        return len(s)

    left = 0
    max_len = 0
    freq = defaultdict(int)

    for right in range(len(s)):
        freq[s[right]] += 1

        # Shrink the window if there are more than two distinct characters
        while len(freq) > 2:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

        # Update the maximum length of the valid window
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len

    return max_len

Explanation

1. Edge Cases: If the string length is ≤ 2, the answer is the length of the string since it can't have more than two distinct characters.
2. Window Expansion: The right pointer expands the window by adding characters to the frequency map.
3. Window Shrinkage: When the number of distinct characters exceeds two, the left pointer moves to the right, reducing the count of the character at the left position. If the count of this character becomes zero, it is removed from the frequency map.
4. Max Length: For each valid window, we calculate its length and update the maximum length if the current window is longer.

Complexity

• Time Complexity: O(n) where n is the length of the string. Each character is processed at most twice (once by the right pointer and once by the left pointer).
• Space Complexity: O(1) since the frequency map can have at most three entries (two distinct characters plus one temporary entry during window adjustment).

This approach efficiently finds the longest substring with at most two distinct characters using the sliding window technique, ensuring optimal performance.

作者声明:本文包含人工智能生成内容。