⚡Flashcard Drill➔
NeetCode #226LC-159MediumSliding WindowNC Algo100
← Back to All Problems

#226 · #159 · Longest Substring with At Most Two Distinct Characters(至多包含两个不同字符的最长子串)

📌 Problem Statement & Constraints

Given a string s, find the length of the longest substring that contains at most two distinct characters. Constraints: 1 <= s.length <= 10^4; s consists of ASCII characters.

💡 Core Algorithmic Approaches

  1. Sliding window with a frequency map: expand the right end and shrink from the left while the map holds more than two distinct characters.
  2. When a character's count drops to zero while shrinking, remove the key so the distinct count is accurate.
  3. The window length is the candidate answer.
  4. This is the k = 2 case of the general At Most K Distinct Characters problem.

💻 Benchmark Python3 Implementation

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)
        l = 0
        best = 0
        for r, ch in enumerate(s):
            cnt[ch] += 1
            while len(cnt) > 2:        # too many distinct characters
                cnt[s[l]] -= 1
                if cnt[s[l]] == 0:
                    del cnt[s[l]]
                l += 1
            best = max(best, r - l + 1)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character enters and leaves the window at most once.
💾 Space Complexity
O(1): the map holds at most 3 entries.

⚠️ Interview Pitfalls & Follow-ups

  • Not deleting zero-count keys: len(cnt) would overcount the distinct characters and the window would shrink too far.
  • Using >= 2 in the while condition: the limit is *at most* two, so the condition is > 2.
  • Tracking the distinct count manually: deleting keys is simpler and less error-prone.
  • Assuming the answer is always 2: a string of a single repeated character gives the whole length.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems