Sliding Window Advanced (Variable Conditions, Frequency Maps, Complex Logic)

Advanced sliding windows combine frequency maps, multi-condition validity, and sometimes atMost(k) - atMost(k-1) tricks for exact counts.

Why this shows up in the real world

Spam detectors combine multiple signals in rolling text windows. Genomics counts k-mers with ambiguous bases using expanded alphabets.

Core idea (explained for students)

Learn the atMost(K) helper pattern: number of subarrays with exactly K distinct = atMost(K) - atMost(K-1). Always verify empty-string and K=0 edge cases.

Try this in Python

from collections import Counter


def at_most_k_distinct(nums: list[int], k: int) -> int:
    ct, L, ans = Counter(), 0, 0
    for R, x in enumerate(nums):
        ct[x] += 1
        while len(ct) > k:
            y = nums[L]
            ct[y] -= 1
            if ct[y] == 0:
                del ct[y]
            L += 1
        ans += R - L + 1
    return ans


def subarrays_exactly_k_distinct(nums: list[int], k: int) -> int:
    return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)


print(subarrays_exactly_k_distinct([1, 2, 1, 2, 3], 2))

Common mistakes

• Off-by-one in the atMost subtraction trick.
• Integer overflow in combinatorial counts.

Key takeaways

• Master exact vs atMost transformations.
• Practice rewriting constraints into monotone predicates.