Exactly K via At Most

Template

Use this when counting subarrays/substrings with exactly k of something.

exactly(k) = atMost(k) - atMost(k - 1)

atMost(k):
    ans = 0
    l = 0
 
    for r = 0; r < n; r++:
        add nums[r]
 
        while window has more than k:
            remove nums[l]
            l++
 
        ans += r - l + 1
 
    return ans

Problems Using This Pattern

Subarrays with K Different Integers

Problem: count subarrays with exactly k distinct values.

At most state: distinct_count <= k.

Count Number of Nice Subarrays

Problem: count subarrays with exactly k odd numbers.

At most state: odd_count <= k.

Binary Subarrays With Sum

Problem: count binary subarrays with sum exactly goal.

At most state: window_sum <= goal.

Substrings Containing Exactly K Distinct Characters

Problem: count substrings with exactly k distinct chars.

At most state: distinct_count <= k.