Count Contiguous Subarrays with Exactly K Distinct Values
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Return the number of nonempty contiguous subarrays of `nums` containing exactly k different integers. Different index intervals count separately even when their value sequences match.
```cpp
class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
Input: nums = [1,2,2,1], k = 2
Output: 5
Explanation: The qualifying intervals are[0,1],[0,2],[0,3],[1,3],and[2,3], using zero-based inclusive indices.
```
**Example 2:**
```text
Input: nums = [1,1,1], k = 1
Output: 6
Explanation: Every nonempty interval contains exactly one distinct value.
```
### Constraints
- `1 <= nums.length <= 2*10^4`.
- `1 <= nums[i],k <= nums.length`.
### Contract considerations
Values and k both lie between1 and the array length. The maximum possible answer fits int for n<=20000;64-bit intermediate counts are still used.
```hint Read the boundary condition
Exactly-k counts can be obtained by subtracting two easier at-most counts.
```
### Boundary reminders
Values and k both lie between1 and the array length. The maximum possible answer fits int for n<=20000;64-bit intermediate counts are still used.
Overview: Count Contiguous Subarrays with Exactly K Distinct Values. Return the number of nonempty contiguous subarrays of nums containing exactly k different integers.