Full lesson preview

Count distinct characters in each window of size K

For each substring (window) of length K, count how many distinct characters it contains.

Python practice7 minStrings – Sliding Window & FrequencyBeginnerLast updated March 25, 2026

Problem statement

Given a string s and an integer k, return a list of integers where the i-th element is the number of distinct characters in the substring s[i:i+k]. If k is greater than the length of s, return an empty list.

Task

Use a sliding-window and frequency map to compute distinct character counts for each window efficiently.

Examples

Example with repeats

Input

s = "abac", k = 2

Output

[2, 2, 2]

Windows: 'ab' -> 2, 'ba' -> 2, 'ac' -> 2 distinct characters each.

Input format

Function count_distinct_in_windows(s: str, k: int) -> list[int]

Output format

Return a list of integers representing distinct counts for each window.

Constraints

0 <= k <= len(s) <= 10^5. Expected O(n) time and O(min(26, n)) extra space for lowercase letters, general O(1) per character set size.

Samples

Sample 1

Input

s = "aaaa", k = 2

Output

[1, 1, 1]

Each window 'aa' has only one distinct character.