Longest Substring with At Most K Distinct Characters
Find the length of the longest substring that contains at most k distinct characters, with a sliding window whose character counts never exceed k keys.
Problem Understanding
Longest Substring with At Most K Distinct Characters (LeetCode 340): given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Examples: s = "eceba", k = 2 → 3 ("ece"); s = "aa", k = 1 → 2.
The Intuition: A Window That Repairs Itself
If a substring has at most k distinct characters, so does every substring inside it. That lets one window sweep the string:
- Grow the window to the right one character at a time, counting characters in a map.
- Too many? When the map holds k + 1 keys, move the left edge right until one character's count hits zero.
- Record the window's length; it is the longest valid one ending at
right.
With k = 2 this is Fruit Into Baskets, and the same grow-and-shrink loop solves Longest Substring Without Repeating Characters.
Interactive Walkthrough
AT MOST 3 DISTINCT IN THE WINDOW
EMPTY WINDOW
0
1
2
3
4
5
6
7
8
9
10
distinct
0
best
:
Answer
:
counts (char × count)
Empty
Empty window. Find the longest substring with at most 3 distinct characters
Next
Add s[0] = "a": 1 distinct
s
k
The shaded cells are the window and the panel on the right is the count map. Watch the left edge chase the extra character out when a (k + 1)-th one arrives, then change k to see the answer move.
Dry Run Table
Input: s = "aabacbebebe", k = 3.
| right | Added | Distinct | Window after shrinking | Length |
|---|---|---|---|---|
| 0–5 | a a b a c b | 3 | "aabacb" | 6 |
| 6 | e | 4 → remove a, a, b, a | "cbe" | 3 |
| 7 | b | 3 | "cbeb" | 4 |
| 8 | e | 3 | "cbebe" | 5 |
| 9 | b | 3 | "cbebeb" | 6 |
| 10 | e | 3 | "cbebebe" | 7 |
Answer: 7.
The Solution Template
A count map for the window; shrink while it has more than k keys.
Longest Substring with At Most K Distinct Characters Code
1var lengthOfLongestSubstringKDistinct = function(s, k) {2 const count = new Map();3 let left = 0, best = 0;4 for (let right = 0; right < s.length; right++) {5 count.set(s[right], (count.get(s[right]) || 0) + 1);6 while (count.size > k) {7 const out = s[left];8 count.set(out, count.get(out) - 1);9 if (count.get(out) === 0) count.delete(out);10 left++;11 }12 best = Math.max(best, right - left + 1);13 }14 return best;15};
Edge Cases & Common Mistakes
- k = 0: the answer is 0; the loop handles it with no special case.
- k at least the number of distinct characters: the whole string is valid, answer
s.length. - Not deleting zero counts: the map size stops meaning "distinct characters in the window".
- Shrinking with
ifinstead ofwhile: one removal may not drop a key, so the window stays invalid. - Recording before shrinking: you would count windows with k + 1 distinct characters.
Summary
Grow the window one character at a time, shrink from the left while the count map has more than k keys, and keep the longest valid window. O(n) time, O(k) space.
More practice: DSA interview questions with answers · patterns cheat sheet