Example
Input
s = 'pqpqs', k = 2
Output
12
There are 12 substrings of 'pqpqs' that contain at most 2 distinct characters.
Full lesson preview
Count substrings with at most K distinct characters
Count how many substrings of a string contain at most K distinct characters using a sliding-window technique that counts valid end positions.
Python practice16 minStrings – Sliding Window & FrequencyIntermediateLast updated March 25, 2026
Problem statement
Given a string s and an integer k, return the number of substrings of s that contain at most k distinct characters. The naive approach enumerates all substrings and checks distinct counts (O(n^2) substrings times cost); instead, use a sliding window where for each right index you add the number of valid substrings ending at that index.
Task
Use a sliding-window plus frequency map to count all substrings with at most K distinct characters in O(n) time.
Examples
Input format
A function call count_substrings_at_most_k_distinct(s, k) where s is a string and k is a non-negative integer.
Output format
An integer representing the count of substrings with at most k distinct characters.
Constraints
0 <= len(s) <= 10^5; 0 <= k <= 10^5. Aim for O(n) time and O(min(n, alphabet)) extra space.
Samples
Sample 1
Input
s = 'abc', k = 2
Output
5
Substrings with <=2 distinct: 'a','ab','b','bc','c' -> 5 total.