Example with K=2
Input
count_substrings_exactly_k("aba", 2)
Output
3
Substrings: 'ab', 'ba', 'aba' each have exactly 2 distinct characters.
Full lesson preview
Count substrings with exactly K distinct characters
Count substrings that contain exactly K distinct characters using the at-most-K trick.
Python practice26 minStrings – Sliding Window & FrequencyAdvancedLast updated March 25, 2026
Problem statement
Given a string s and an integer K, return the number of substrings of s that contain exactly K distinct characters. Use a sliding-window approach to count substrings with at most K distinct characters and get the exact count by subtracting counts for at most (K-1) distinct characters.
For example, s='pqpqs', K=2 -> substrings with exactly 2 distinct characters are: 'pq','pqp','qp','qpq','pq','pqs','qs' -> 7.
Task
Implement an efficient sliding-window solution that counts substrings with exactly K distinct characters by computing at-most-K and using subtraction.
Examples
Input format
Function call: count_substrings_exactly_k(s, k) where s is a string and k is a non-negative integer.
Output format
Return an integer: number of substrings with exactly k distinct characters.
Constraints
0 <= k <= 26, 0 <= len(s) <= 2000. s may contain lowercase and/or uppercase letters; treat characters distinctly.
Samples
Sample 1
Input
count_substrings_exactly_k("abc", 2)
Output
2
Substrings: 'ab' and 'bc'.