Longest Window With K Distinct Characters

L4 Easy Sliding Window

Concept

Count how many distinct characters a window holds. A dictionary mapping character to count lets the window shrink until the distinct count drops back to k.

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters. If k is zero, no character may appear, so the answer is 0.

Examples

▸ s = "araaci", k = 2

→ 4

▸ s = "araaci", k = 1

→ 2

▸ s = "cbbebi", k = 3

→ 5

Progressive Hints

Hint 1 · Nudge

Count the characters inside the window, and drop from the left until you're back to k.

Hint 2 · Plan

Keep counts of the characters currently in the window and a left pointer. For each character on the right, add to its count. While more than k distinct characters are present, remove the leftmost character from the counts and advance the left pointer. Record the window size each step.

Hint 3 · Approach

counts = map of counts, left = 0, best = 0. For each right, c: counts[c] = counts[c] + 1. While the number of distinct characters is above k: drop s[left] from counts (removing it at 0) and advance left. best = the larger of best and right - left + 1. Return best, or 0 when k is 0.

Output

// Run your code to see the output here.