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
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 = −1Answer 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#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int longest_k_distinct(const string& s, int k) {
array<int, 256> count{};
int left = 0, best = 0, distinct = 0;
for (int r = 0; r < (int)s.size(); ++r) {
if (count[(unsigned char)s[r]]++ == 0) ++distinct;
while (distinct > k)
if (--count[(unsigned char)s[left++]] == 0) --distinct;
best = max(best, r - left + 1);
}
return best;
}