Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Hints

· Stuck? Reveal one nudge at a time.

This is Fruit Into Baskets with k baskets instead of two.

Keep a count map of the window's characters; its size is the distinct count.

Grow the right edge; when the map has more than k keys, shrink from the left.

Common doubts

Only the threshold: fruit fixes it at 2, this compares the count-map size to a parameter k. The algorithm is otherwise identical.

So the map's key-count stays equal to the number of distinct characters currently in the window.

Zero — no character is permitted, so the shrink loop empties any window immediately and the best stays 0.

Interview follow-ups

· What an interviewer asks next.

Compute 'at most k' minus 'at most k-1' — the count of substrings (or lengths) with exactly k distinct falls out of two at-most windows.

The map never holds more than k+1 entries, so space is O(k) — independent of the string length.

Fun facts

The 'at most k distinct' window is a workhorse: fruit baskets, this problem, and 'subarrays with exactly k distinct' all reduce to it.
Subtracting two at-most-k windows to get exactly-k is a neat inclusion-exclusion trick worth remembering.

Asked at

GoogleAmazonMetaMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: s = "eceba", k = 2
Output: 3
The longest substring with at most 2 distinct characters is "ece", of length 3.

Example 2

Input: s = "aa", k = 1
Output: 2
The whole string "aa" has one distinct character.

Constraints

- 0 <= s.length <= 5 * 10^4 - 0 <= k <= 50 - s consists of lowercase English letters.

This is the general form of the two-basket problem: instead of at most two distinct values, allow at most k. The window and its character-count map are identical — you just compare the map's size against k.

Prerequisites

Before you start

· Concepts used directly in the solution.

Variable window. Growing and shrinking a window to keep a condition true.

Count map. A map of character -> occurrences, whose size is the number of distinct characters in the window.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definitions

“At most k, or exactly k, distinct?”

At most — fewer than k distinct is fine.

“What if k is 0?”

No characters are allowed, so the answer is 0.

The ideal opening — say it like this

This is the at-most-k-distinct window — the same as fruit baskets but with k instead of two.

I keep a count map of the characters in the window and grow the right edge.

When the map has more than k keys, I shrink from the left until it's back to k, tracking the longest width.

Understand the problem

Worked example — s = "eceba", k = 2

right=0 e   {e}       best 1
right=1 c   {e,c}     best 2
right=2 e   {e,c}     best 3   (window "ece")
right=3 b   {e,c,b}!  shrink -> {c,b}? no, drop e's: -> {b, ...}; window "eb" best 3
right=4 a   {b,a}     best 3
answer: 3

Key observations

1Aha

Map size is the distinct count

The number of keys in the count map equals the number of distinct characters in the window — the exact quantity you cap at k.

2Aha

Delete a character at count zero

As you shrink, a character truly leaves the window only when its count reaches zero; deleting it then keeps the map size accurate.

3Aha

Same template, parameter k

Fruit Into Baskets is this with k = 2. Nothing about the algorithm changes except the threshold you compare the map size against.

Brute force vs optimal

	Extend from each start	Sliding window
Idea	From each index, extend while <= k distinct	One window, shrink when > k distinct
Time	O(n^2)	O(n)
Space	O(k)	O(k)

The brute rebuilds the distinct set from each index; the window carries a count map forward with both pointers moving right only. Full code is in the Approaches selector below.

Summary

Key takeaway

Longest substring with at most k distinct characters: grow a window with a character-count map; when the map exceeds k keys, shrink from the left until it's back to k, tracking the longest width. It's Fruit Into Baskets with a parameter — O(n) time, O(k) space.

count = {}; left = 0; best = 0
for right in 0 .. n-1:
    count[s[right]] += 1
    while len(count) > k: count[s[left]] -= 1; drop if 0; left += 1
    best = max(best, right - left + 1)
return best