Longest Run With At Most K Kinds
MediumSliding Window
Problem
A conveyor belt carries items labelled by lowercase letters, given as the string s. A sorting robot has k bins and each bin can only take one label.
Return the length of the longest contiguous section of the belt that the robot can process, that is, the longest substring of s containing at most `k` distinct letters.
Example 1
- Input:
- s = "abaccc", k = 2
- Output:
- 4
"accc" uses only a and c. "abac" would need three bins.
Example 2
- Input:
- s = "aaaa", k = 1
- Output:
- 4
Constraints
- 0 ≤ s.length ≤ 10^5
- 0 ≤ k ≤ 26
- s contains only lowercase English letters.
Hint
Show the first hint
If a substring has at most k kinds, every substring inside it does too.
Walkthrough
How to approach it
01Clarify before coding
- Can k be 0? Yes; then no non-empty substring qualifies, so return 0.
- Can k be larger than the number of distinct letters? Yes; then the whole string qualifies.
- Substring, not subsequence? Yes, contiguous.
02Brute force
For each start, extend to the right while the set of letters has at most k members, and record the longest.
Cost: O(n²) time in the worst case (e.g. k = 26 on a long string), too slow for 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.