Editorial for K-Distinct Windows

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Maintain the frequency of each value inside the current window of length $x$ ~x~, along with the number of distinct values whose frequency is positive.

First build the window covering positions $1$ ~1~ through $x$ ~x~. Then slide the window one step at a time:

remove the value leaving the window;
add the value entering the window;
update the distinct-count when a frequency changes between $0$ ~0~ and $1$ ~1~.

Each window is processed in $O(1)$ ~O(1)~ amortized time, so the full scan is $O(n)$ ~O(n)~ time.

Solution (Python)

from collections import defaultdict


n, x, k = map(int, input().split())
values = list(map(int, input().split()))

freq: dict[int, int] = defaultdict(int)
distinct = 0

for i in range(x):
    if freq[values[i]] == 0:
        distinct += 1
    freq[values[i]] += 1

answer = 1 if distinct >= k else 0

for right in range(x, n):
    left_value = values[right - x]
    freq[left_value] -= 1
    if freq[left_value] == 0:
        distinct -= 1

    if freq[values[right]] == 0:
        distinct += 1
    freq[values[right]] += 1

    if distinct >= k:
        answer += 1

print(answer)

Comments

There are no comments at the moment.