Count Substrings At Most K Distinct

Return the number of non-empty substrings of s that contain at most k distinct characters.

countAtMostKDistinct(s, k)

Input format: s | k.

Examples

s="abc", k=2    // → 5   (a, b, c, ab, bc)
s="aa", k=1     // → 3   (a, a, aa)
s="abc", k=0    // → 0

Walkthrough

Thinking it through

You need to count every substring with at most k distinct characters. Checking each substring directly and counting distinct characters from scratch is O(n²) substrings — wasteful since consecutive candidates overlap almost entirely.

Recognizing the monotonic structure

For a fixed ending position, growing the substring leftward only ever keeps the distinct count the same or grows it — never shrinks. Equivalently, shrinking from the left only keeps it the same or decreases it. That monotonic relationship is what makes a two-pointer window valid: there's a clean boundary left where everything from left to right has at most k distinct characters.

The specific shrink condition

Maintain a running frequency map. When a new character pushes the distinct count above k, shrink from the left — decrement, delete if zero, advance — until the count is k or fewer.

Counting without enumerating every substring

Once [left, right] is valid, every substring ending at right and starting anywhere from left to right is also valid, since starting further right only removes characters and can't increase distinctness. Count them all at once: there are right - left + 1 of them.

Building the approach

Expand by including s[right], updating the map.
While the map has more than k keys, shrink from the left.
Add right - left + 1 to the running total.
Repeat for every right.

Why this is efficient

Both pointers move forward monotonically — O(n) total. The batch count (right - left + 1) replaces an O(n) inner enumeration, collapsing total work from O(n²) to O(n).

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.