Workspace

Problem workspace

3 day streakD

Longest Substring with At Most K Distinct

MediumSliding WindowLongest windows

The challenge

Return the longest substring length containing at most k distinct characters. Characters may repeat.

Strings contain ASCII characters; indices are zero-based. C++17 or later. k ≥ 0.

Example

eceba, k = 2 → 3, from ece.

Use the walkthrough below to inspect the input and each state change.

See At most K distinct, step by step

Expand, shrink, and inspect the window state.

5 elements · zero-based indicesk = 2
Sliding window over 5 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1e0c1e2b3a4
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 15

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

0
View exact input

Input: ["e","c","e","b","a"] · k = 2

Current window is empty.

Put it into code

Maintain exact character frequencies. A character stops contributing to distinct count only when its frequency reaches zero. For a fruit-basket problem, the same rule uses k = 2.

Indices are zero-based. C++ uses C++17 or later.

def longest_k_distinct(s, k):
    count = {}
    left = best = 0
    for right, char in enumerate(s):
        count[char] = count.get(char, 0) + 1
        while len(count) > k:
            old = s[left]
            count[old] -= 1
            if count[old] == 0:
                del count[old]
            left += 1
        best = max(best, right - left + 1)
    return best

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap