1. Brute Force

Intuition

The most direct approach is to examine every possible substring and check if it contains at most two distinct characters. For each starting position, we extend the substring character by character, tracking the distinct characters seen. Once we see a third distinct character, we stop and record the maximum valid length found.

Algorithm

1. Initialize res = 0 to store the maximum length.
2. For each starting index i from 0 to n-1:
   • Create a set seen to track distinct characters.
   • Initialize curLen = 0.
   • For each ending index j from i to n-1:
     • Add s[j] to the set.
     • If the set size exceeds 2, break out of the inner loop.
     • Otherwise, increment curLen.
   • Update res = max(res, curLen).
3. Return res.

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

Intuition

We maintain a window that always contains at most two distinct characters. As we expand the window to the right, we track character frequencies in a hash map. When adding a new character causes us to have more than two distinct characters, we shrink the window from the left until we're back to two or fewer distinct characters.

Algorithm

1. Initialize res = 0, j = 0 (left pointer), and a hash map seen for character counts.
2. For each i (right pointer) from 0 to n-1:
   • Increment the count of s[i] in the map.
   • While the map contains more than 2 distinct characters:
     • Decrement the count of s[j].
     • If the count reaches 0, remove s[j] from the map.
     • Increment j.
   • Update res = max(res, i - j + 1).
3. Return res.

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)

Intuition

We can further optimize by observing that we only care about the maximum window size. Instead of tracking the actual maximum during iteration, we maintain a window that never shrinks by more than one element at a time. When we have too many distinct characters, we shift the entire window right by one. The final window size represents the longest valid substring.

Algorithm

1. Initialize j = 0 (left pointer) and a hash map count for character frequencies.
2. For each i from 0 to n-1:
   • Increment the count of s[i].
   • If more than 2 distinct characters:
     • Decrement the count of s[j].
     • If count becomes 0, remove from map.
     • Increment j.
3. Return i - j + 1 (or n - j after the loop).

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.

---

Common Pitfalls

Forgetting to Remove Characters with Zero Count

When shrinking the window from the left, you must remove characters from the hash map when their count drops to zero. If you only decrement the count without removing the entry, the map size will incorrectly reflect more distinct characters than actually exist in the window, causing premature window shrinking.

Confusing "At Most Two" with "Exactly Two"

The problem asks for substrings with at most two distinct characters, not exactly two. This means substrings with zero or one distinct character are also valid. Ensure your solution counts these cases correctly and does not skip windows with fewer than two distinct characters.

Incorrect Window Boundary Updates

A common mistake is updating the result before fully adjusting the window to be valid. Always ensure the window contains at most two distinct characters before calculating and updating the maximum length. Update the result after the while loop that shrinks the window, not before.