Count Number of Substrings

Given a lowercase string s and an integer K, count the number of substrings of s that contain exactly K distinct characters. A substring is a contiguous run…

Given a lowercase string `s` and an integer `K`, count the number of **substrings** of `s` that contain **exactly** `K` distinct characters. A substring is a contiguous run of characters. Indexing is **0-based**. Counting "exactly K distinct" directly is awkward — a single sliding window can bound the distinct count only from above. The trick is: exactlyK(s, K) = atMostK(s, K) − atMostK(s, K − 1) where `atMostK(s, k)` counts the substrings that contain **at most** `k` distinct characters. `atMostK` is computed with one sliding window: expand a right pointer adding `s[right]` to a frequency map; while the number of distinct characters exceeds `k`, shrink from the left removing `s[left]`; at every `right`, every window `[left..right]` is valid, so add `(right − left + 1)` to the count. If `k < 0`, `atMostK` returns 0. Subtracting the two at-most counts leaves exactly the substrings whose distinct-character count is precisely `K`. **Example:** `s = "aba"`, `K = 2`. atMostK(2) = 6, atMostK(1) = 3, so the answer is `6 − 3 = 3` (the substrings "ab", "ba", "aba").

- `1 <= s.length <= 10^5` - `s` consists only of lowercase English letters. - `1 <= K <= 26` - The answer is a signed 64-bit integer (`long long` in C++, `long` in Java). - The interactive visualizer accepts 1–15 characters; longer valid inputs are execution-only.

Example 1: input s = "abc", K = 2; output 2. Substrings with exactly 2 distinct characters are "ab" and "bc".

Example 2: input s = "aba", K = 2; output 3. Substrings with exactly 2 distinct characters are "ab", "ba", and "aba".

Example 3: input s = "aaa", K = 1; output 6. Every one of the 6 substrings of "aaa" has exactly 1 distinct character.

Category: Strings. Topic: strings. Difficulty: Hard. Patterns: sliding-window.