309. How Many Stretches Have At Most K Values
Challenge1000 ms256 MBSolved by 0%
Print how many contiguous stretches contain at most k distinct values.
1 2 1 2 3, k = 2 -> 12
The counting trick is the point. Slide a window that always satisfies the
condition, and when it ends at index i starting no earlier than start,
every stretch ending at i and beginning at or after start is valid. That
is i - start + 1 of them, added in one step rather than enumerated.
Adding a window length at every position is what turns an O(n^2)
enumeration into a single pass.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the number of stretches with at most k distinct values.
Input5 2
1 2 1 2 3
Output12
Noteis the worked example
Input1 1
1
Output1
Noteis a single element and a single stretch
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.