685. Counting Stretches With Exactly k Distinct Values
Print how many contiguous stretches contain EXACTLY k distinct values.
Overlapping stretches each count separately.
A window cannot answer this directly. "Exactly k" is not monotonic: widening a
window can take the distinct count past k and no further widening brings it
back, so there is no single moment at which to move the left edge.
"At most k" IS monotonic, and the way through is a subtraction:
exactly(k) = atMost(k) - atMost(k - 1)
Every stretch with at most k distinct values either has exactly k or has at
most k - 1, and the two groups do not overlap, so subtracting leaves exactly
what was wanted.
Problem #309 computes atMost. This is that function called twice, and the
technique of converting an exact condition into a difference of monotone ones
appears far beyond windows.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ n` - `1 ≤ value ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n space-separated integers.
Output
Print one integer: how many contiguous stretches contain exactly k distinct values.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.