704. The Heaviest Window of k Different Values
Among the windows of length EXACTLY k whose k values are all different, print the largest
total. Print 0 when no such window exists.
1 5 4 2 9 9 9, k = 3 -> 15 the window 4 2 9; the heavier 9 9 9 repeats
4 4 4, k = 3 -> 0
2 6 7 3 1 7, k = 4 -> 18
## Two things at once
The window length is fixed, so nothing grows or shrinks. But a fixed window still has to carry TWO quantities: its running total, and whether it currently holds a duplicate.
Carrying a validity flag alongside the usual sum is the step worth taking away. It is what lets a fixed-size slide answer a question the length alone cannot.
## Counting duplicates without rescanning
Keep a tally of how many times each value is inside, plus a single number dup, the count of
values whose tally is at least 2.
on entry: c[v] += 1; if c[v] == 2: dup += 1
on exit: c[u] -= 1; if c[u] == 1: dup -= 1
The window is duplicate-free exactly when dup == 0. Both updates are O(1), so the slide
stays linear.
Testing "are all k values different" from scratch per window is O(n * k) and is the version
that times out.
## Why the two tests are 2 and 1, not 1 and 0
A value becomes a duplicate the moment its tally REACHES 2, and stops being one the moment its
tally drops back to 1. Writing == 1 on entry counts every value as a duplicate; writing
== 0 on exit never decrements at all.
## The shape of the loop
for hi in 0 .. n-1:
add a[hi]
if hi >= k: remove a[hi - k]
if hi >= k - 1 and dup == 0: best = max(best, total)
The window is only complete from index k - 1 onward, so nothing is recorded before then.
## Boundaries
k = 1 answers the largest single value. k larger than the number of distinct values in the
array answers 0, and 4 4 4 with k = 3 is that case.
## Overflow
200000 values of up to 2000 total 4 * 10^8, comfortably inside the 2147483647 a
signed 32 bit integer holds. This problem has no overflow.
The figure is worth computing rather than carrying over from a neighbouring problem. With a
value cap of 10^4 the total would be 2 * 10^9, which still fits; only at 10^5 does
it reach 2 * 10^10 and genuinely need 64 bits.
## Cost
Time O(n). Space O(V) for the tally.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `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 largest total of a duplicate-free window of length k, or 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.