At most k distinct in the window
Updated
Expand R, adding a[R] (or s[R]) to counts. While distinct > k, drop a[L] and L++. Every remaining window has at most k different values.
What to focus on
Record length only while distinct ≤ k. k=1 is a single run of one value. Distinct is not length.
Worked examples
k=2 array
a = [1, 2, 1, 3], k=2- [1,2,1] distinct 2 len 3
- add 3 → distinct 3, drop 1 → [2,1,3] still 3
- drop 2 → [1,3] distinct 2
Result: best length 3
k=2 string
s = "abca", k=2- ab len 2
- abc distinct 3 drop a → bc
- bca distinct 3 drop b → ca
Result: best length 2
k=2 on repeats
s = "abcabcbb", k=2- abc too many, shrink to 2 distinct
- R=7 window s[4..7]="bcbb" distinct 2
Result: best length 4
Try it
Write longestAtMostK(a, k). a is an array of integers, or s is a string. k is the distinct limit. L is the left index. R is the right index. The window includes a[L..R]. Valid means distinct ≤ k. Return the best length. Trace [1, 2, 1, 3] k=2, "abca" k=2, and "abcabcbb" k=2.
a (or s) is nonempty. k ≥ 1. The alphabet has at least k distinct values.