PPractick

The problem

A genetics lab scans DNA-like strings and wants to know how many substrings contain exactly K different symbols, a measure of local diversity. Checking every substring is O(n²) or worse. The key trick is that "exactly K" is awkward for a sliding window, but "at most K" is easy: for each right end, the window of valid left ends is a single range. So compute atMost(K) − atMost(K − 1), where each term is a linear sliding window.

Example: ("aba", 2) → 3 (the substrings "ab", "ba" and "aba").

Function signature

long long countExactlyK(const string& s, int k);  // lowercase letters

Test cases

Input (s, k)	Output	Explanation
("aba", 2)	3	"ab", "ba", "aba"
("abaaca", 1)	7	Runs a, b, aa (3 substrings), c, a
("abc", 3)	1	Only "abc"
("aa", 1)	3	"a", "a", "aa"
("abc", 4)	0	Only 3 distinct letters exist
("abcbaa", 3)	8	Every substring containing a, b and c

(Confirm: substrings are counted by position, so equal substrings at different positions count separately; lowercase letters only.)

How interviewers phrase it

• "Count the substrings with exactly K distinct characters" (GeeksforGeeks).
• The array version: "subarrays with K different integers" (LeetCode 992, Hard).
• The same "exactly = atMost(K) − atMost(K − 1)" trick solves "binary subarrays with sum" and "count nice subarrays".

Clarifying questions to ask

1. Are substrings counted by position (duplicates count separately)?
2. What's the character set?
3. How large can n be? (The count can reach about n²/2.)

Follow-ups to expect

1. "Why not slide a window for 'exactly K' directly?"
2. "Why does atMost(K) − atMost(K − 1) give exactly K?"
3. "How does atMost count substrings?"
4. "Complexity?"

Related questions

• Longest Substring Without Repeating Characters Medium
• Longest Repeating Character Replacement Hard
• Number of Substrings Containing All Three Characters Hard
• Longest Substring With At Most K Distinct Characters Hard
• Minimum Window Substring Hard
• Minimum Window Subsequence Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in