Exactly K Distinct

Difficulty: 1900 4000 ms 128 MB

two-pointers

Count the contiguous subarrays containing EXACTLY K distinct values.

Input: the first line has N and K; the second line has N integers.

Output: the number of subarrays with exactly K distinct values.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ N
• 1 ≤ a_i ≤ 10⁹

Sample Tests

4 2
1 2 1 3

4

3 1
5 5 5

6

Read the Editorial