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
- Sliding window with a frequency map: expand the right end and shrink from the left while the map holds more than two distinct characters.
- When a character's count drops to zero while shrinking, remove the key so the distinct count is accurate.
- The window length is the candidate answer.
- This is the
k = 2case 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
>= 2in 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.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner