Ctrl K

Stretches With Exactly k Kinds

Hard
You are given an integer array values and an integer kinds. Count the non-empty windows of the array (runs of consecutive elements) that contain **exactly** kinds distinct values. Windows at different positions count separately, even if they hold the same numbers.
Example 1
values=[2, 1, 2, 3], kinds=2 → 4

Exactly two distinct values appear in [2, 1], [1, 2], [2, 3] and [2, 1, 2].

Example 2
values=[3, 3, 3], kinds=1 → 6

Each of the six windows is made of 3s only.

Example 3
values=[1, 2, 1], kinds=3 → 0

The array has only two distinct values, so three is out of reach.

Constraints
  • 1 ≤ len(values) ≤ 2·10⁴
  • 1 ≤ values[i] ≤ len(values)
  • 1 ≤ kinds ≤ len(values)
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsValues One Apart EasyMoving Window Median HardNarrowest Range Touching Every List HardA Run With No Gaps HardBalanced Cuts After One Replacement Hard
loading Python…
Input
values=[2, 1, 2, 3], kinds=2
Expected
4

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.