We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Substring with At Most Two Distinct Characters

Number: 159

Difficulty: Medium

Paid? Yes

Companies: TikTok, Google, Yandex

Problem Description

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

Key Insights

  • Use a sliding window to maintain a contiguous substring.
  • Keep track of character frequencies within the current window using a hash map or dictionary.
  • When the window contains more than two distinct characters, shrink the window from the left until only two remain.
  • Update the maximum length each time the window satisfies the condition.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, since each character is processed at most twice. Space Complexity: O(1) because the hash map holds at most 3 entries (usually up to 2 distinct characters).

Solution

We use the sliding window technique with two pointers (left and right) to represent the current window. A hash table/dictionary records the count of each character inside the window. As we extend the right pointer, we update the count. If the hash table contains more than two distinct characters, we start moving the left pointer to reduce the number of distinct characters until we have at most two distinct keys. The length of the current valid window is then used to update our maximum length answer.

Code Solutions

# Python solution for Longest Substring with At Most Two Distinct Characters
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        left = 0  # Initialize left pointer of the window
        max_length = 0  # Variable to store the maximum window size found
        char_count = {}  # Dictionary to count characters in the current window
        
        for right, char in enumerate(s):
            # Add the current character to the window (increase count)
            char_count[char] = char_count.get(char, 0) + 1
            
            # If there are more than two distinct characters, shrink the window from the left
            while len(char_count) > 2:
                left_char = s[left]
                char_count[left_char] -= 1
                if char_count[left_char] == 0:
                    del char_count[left_char]
                left += 1
            
            # Update max_length if current window is larger
            max_length = max(max_length, right - left + 1)
            
        return max_length
← Back to All Questions