Segments with Exactly k Kinds

A collector's shelf holds items in a row; kinds[i] is the category of item i. Return the number of contiguous segments of the shelf that contain exactly k different categories.

Examples

Input:  kinds = [1, 2, 1, 2, 3], k = 2
Output: 7
Explanation: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Input:  kinds = [1, 2, 1, 3, 4], k = 3
Output: 3
Explanation: [1,2,1,3], [2,1,3], [1,3,4].

Constraints

• 1 <= len(kinds) <= 10**5
• 1 <= kinds[i] <= 10**9, 1 <= k <= len(kinds)
• Target complexity: O(n) time; enumerating all segments and counting categories is far too slow for the largest tests.

Goals

• Count subarrays with at most k distinct values in one pass
• Combine two 'at most' counts into an 'exactly' count