159. Longest Substring with At Most Two Distinct Characters - Explanation

Description

You are given a string s, return the length of the longest substring that contains at most two distinct characters.

Note: A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "eceba"

Output: 3

Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"

Output: 5

Explanation: The substring is "aabbb" which its length is 5.

Constraints:

0 <= s.length <= 1,00,000
s consists of English letters.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        res, n = 0, len(s)

        for i in range(n):
            seen = set()
            cnt = curLen = 0
            for j in range(i, n):
                seen.add(s[j])
                if len(seen) > 2:
                    break
                curLen += 1
            res = max(res, curLen)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ since we have at most $52$ different characters.

2. Sliding Window

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        res, n = 0, len(s)
        seen = defaultdict(int)
        j = 0

        for i in range(n):
            seen[s[i]] += 1
            while len(seen) > 2:
                seen[s[j]] -= 1
                if seen[s[j]] == 0:
                    seen.pop(s[j])
                j += 1
            res = max(res, i - j + 1)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we have at most $52$ different characters.

3. Sliding Window (Optimal)

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        n = len(s)
        count = defaultdict(int)
        j = 0

        for i in range(n):
            count[s[i]] += 1
            if len(count) > 2:
                count[s[j]] -= 1
                if count[s[j]] == 0:
                    count.pop(s[j])
                j += 1
        return i - j + 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we have at most $52$ different characters.