Longest Substring with At Most K Distinct

LeetCode 340 • Hard • Sliding Window

Input: s = "eceba", k = 2 → Output: 3 (ece or eba). Sliding window + char count map. Shrink when distinct > k.

TimeO(n)

SpaceO(k)

left: — right: — maxLen: —

Window

Right

Shrink

left—

right—

count—

maxLen—

Speed:

Ready

Press Play. Sliding window: expand right, add to count map. If distinct > k, shrink from left until valid.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Sliding window + count map. Shrink when distinct > k.

═══ LONGEST SUBSTRING K DISTINCT — SLIDING WINDOW ═══

PATTERN ▸ Sliding window + count map (hash) O(n) · O(k)

① INIT

count = {}, left = 0, max_len = 0

② EXPAND RIGHT

for right, c in enumerate(s): count[c] = count.get(c,0) + 1

③ SHRINK WHILE distinct > k

while len(count) > k: d = s[left]; count[d]-=1; if count[d]==0: del count[d]; left+=1

④ UPDATE

max_len = max(max_len, right - left + 1)

⑤ RETURN

return max_len

your implementation

Verify: