⚡Flashcard Drill➔
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

  1. Generalise the two-distinct-character window: shrink while the map holds more than k distinct characters.
  2. Delete keys whose count reaches zero so the distinct count stays accurate.
  3. The window length is the candidate answer.
  4. With k = 0 the 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 == 0 guard: 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 >= k in 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems