Return the number of non-empty substrings of s that contain exactly k
distinct characters.
countExactlyKDistinct(s, k)
Input format: s | k.
s="abc", k=2 // → 2 (ab, bc)
s="aabb", k=2 // → 4 (aab, abb, ab, ... actually: ab, aab, abb, aabb)
s="abc", k=0 // → 0
You need substrings with exactly k distinct characters. "Exactly" doesn't have the same clean monotonic structure that made the "at most k" window trick work: valid and invalid windows for a fixed ending point aren't a single contiguous range, so a plain two-pointer scan can't capture it in one pass.
Substrings with at most k distinct characters, minus substrings with at most k-1 distinct, leaves exactly those with precisely k — every "at most k" substring either has exactly k or fewer, and the second count captures the "fewer" group exactly.
A single-window "exactly k" attempt would need two failure modes at once (too many distinct, and after shrinking, too few) that don't combine into one monotonic window. "At most k" is a problem you already know how to solve cleanly: growing the window only ever increases or holds the distinct count, so there's always a clean valid/invalid boundary.
m distinct characters, using the standard window: expand, shrink from the left when the count exceeds m, add right - left + 1 each step.m = k and m = k - 1.atMost(k) - atMost(k-1).k - 1 negative (when k is 0) as zero substrings, since no non-empty substring can have negative distinct characters.Each call is a standard O(n) sliding-window scan, so two calls together are still O(n) overall. "Exactly X" = "at most X" minus "at most X-1" is a broadly useful decomposition whenever a target condition lacks a clean monotonic window on its own, but a cumulative version of it does.
def count_exactly_k_distinct(s, k):
def at_most(limit):
if limit < 0:
return 0
count = {}
left = 0
total = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
while len(count) > limit:
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
total += right - left + 1
return total
return at_most(k) - at_most(k - 1)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.