AlgoViz
HomeSliding Window

Longest Substring With At Most K Distinct Characters

Hard

Shrink while the map holds too many keys

Problem

Return the length of the longest substring with at most k distinct characters.

In simple words

Slide a window that keeps at most k distinct letters, shrinking from the left when a new one overflows it.

The idea

Expand right adding characters to a frequency map, and while the map holds more than k keys shrink from the left. The map's size is the number of distinct characters, so the validity test is a single comparison.

The trick

  • Delete a key when its count hits zero, or the size overstates the distinct count.
  • Record the answer after each shrink loop, when the window is valid again.
e
c
e
b
a
0
1
2
3
4
k2

Step 1 of 12. Brute force: from each start, extend while at most 2 distinct values appear. Values: e, c, e, b, a. k 2.

1/12
Brute force
timeO(n²)spaceO(k)

Every window.

1for (let i = 0; i < n; i++) {2  const seen = new Set();3  for (let j = i; j < n; j++) {4    seen.add(s[j]);5    if (seen.size > k) break;6    best = Math.max(best, j - i + 1);7  }8}

Input

array
[e, c, e, b, a]

Memory

k
2

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "eceba", k = 2
Output:
3
Explanation:
"ece" uses 2 letters → length 3.

Example 2

Input:
s = "aa", k = 1
Output:
2
Explanation:
Both a's fit one distinct letter.

Example 3

Input:
s = "abcabc", k = 2
Output:
2
Explanation:
Best two-letter window is length 2.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.