687. The Longest Stretch Where Nothing Repeats Too Often
Find the longest contiguous stretch in which NO value appears more than k times, and print
its length.
1 2 1 2 3, k = 2 -> 5 each of 1 and 2 appears twice
1 2 1 2 1, k = 2 -> 4 the stretch 2 1 2 1
4 4 1 4 4, k = 2 -> 3 the stretch 4 1 4
1 1 1 1, k = 1 -> 1
## This is not the "at most k distinct" question
Problem 303 caps how many DIFFERENT values the window may hold. This caps how many TIMES each value may appear. They read almost the same and they are not the same at all.
1 2 1 2 3 with k = 2 holds three different values, so 303 would reject it; here every
value appears at most twice, so the whole array qualifies and the answer is 5.
Reading the invariant off the statement precisely, before writing any code, is the exercise.
## Only one count can be in violation
Keep a tally of how many times each value is inside the window. When a[hi] is added, the
only count that can have risen is a[hi]'s, so it is the only one that can be over the cap.
That is why the shrink condition is a single lookup and not a scan of the tally:
for hi in 0 .. n-1:
count[a[hi]] += 1
while count[a[hi]] > k:
count[a[lo]] -= 1; lo += 1
best = max(best, hi - lo + 1)
The loop stops as soon as a copy of a[hi] itself leaves, because until then the offending
count has not changed. Removing other values first is harmless and unavoidable; they sit to the
left of that copy and have to go anyway.
## Why the left edge never returns
Growing on the right can only raise a count, never lower one, so a legal window can only be broken by an addition. Shrinking on the left only lowers counts, so it never breaks anything. The left edge therefore moves forward only, and each index enters and leaves once.
That argument is the whole justification for a sliding window, and it is worth being able to give it, because linear running time is not obvious from code with a loop inside a loop.
## Boundaries
k at least the largest number of times any value appears gives n.
k = 1 forbids repeats entirely, which is the invariant problem 692 works under.
A single value always answers 1.
## Cost
Time O(n). Space O(V) for the tally.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ n` - `1 ≤ each value ≤ 2000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the length of the longest qualifying stretch.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.