Subarrays With Exactly K Distinct

A subarray is a run of one or more numbers next to each other in a list. Write count_exactly_k(nums, k) that returns how many subarrays of nums contain exactly k different values. Subarrays at different positions count separately, even when they hold the same values.

Examples

count_exactly_k([1, 2, 1, 3], 2)   # returns 4
count_exactly_k([5, 5, 5], 1)      # returns 6
count_exactly_k([1, 2, 3], 3)      # returns 1

In the first example the subarrays [1, 2], [2, 1], [1, 3] and [1, 2, 1] each hold two different values. In the second, all 6 subarrays of [5, 5, 5] hold only the value 5.

Constraints

• 0 <= len(nums) <= 20,000
• 1 <= k <= 20,000
• -10^9 <= nums[i] <= 10^9

Note

20,000 numbers have about 200 million subarrays. Aim for a few passes over the list.