Loading section...

Multi-Constraint Windows and the Complement Trick

Concepts: pyComplementTrick, pyMultiConstraintWindow, pyExactKDistinct

Most sliding window problems have a monotonic property: as the window grows, the constraint either stays satisfied or becomes violated. That's why expand-contract works -- you expand until violated, then contract until satisfied. Exact-count constraints break this monotonicity. A window with exactly K distinct characters might become valid, then invalid (too many), then valid again as you expand. The standard framework doesn't handle this cleanly. The Complement Trick The complement trick is this: count(exactly K) = count(at-most K) minus count(at-most K-1). The 'at-most-K' version IS monotonic -- as the window grows, distinct count only increases, so the contract step is well-defined. You implement 'at-most-K' once as a clean helper, then call it twice with K and K-1 and subtract. This is