NeetCode #227LC-340MediumSliding WindowNC Algo100
← Back to All Problems#227 · #340 · Longest Substring with At Most K Distinct Characters(至多包含 K 个不同字符的最长子串)
📌 Problem Statement & Constraints
Given a string
s and an integer k, return the length of the longest substring that contains at most k distinct characters. Constraints: 1 <= s.length <= 5 * 10^4, 0 <= k <= 50; s consists of ASCII characters.💡 Core Algorithmic Approaches
- Generalise the two-distinct-character window: shrink while the map holds more than
kdistinct characters. - Delete keys whose count reaches zero so the distinct count stays accurate.
- The window length is the candidate answer.
- With
k = 0the answer is 0, which the general code handles if the window never becomes non-empty -- verify that the shrink loop empties it.
💻 Benchmark Python3 Implementation
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
from collections import defaultdict
if k == 0:
return 0 # no character is allowed
cnt = defaultdict(int)
l = 0
best = 0
for r, ch in enumerate(s):
cnt[ch] += 1
while len(cnt) > k:
cnt[s[l]] -= 1
if cnt[s[l]] == 0:
del cnt[s[l]] # keep the distinct count accurate
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(k) for the frequency map.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
k == 0guard: without it, the shrink loop would empty the window every iteration and the answer would still be 0, but the extra work is pointless -- and in some formulations the loop could misbehave. - Not deleting zero-count keys: the distinct count would be wrong.
- Assuming the alphabet is small: the general map-based approach works for any alphabet, unlike a fixed 26-array.
- Using
>= kin the condition: the limit is *at most*k.
⚡
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