How does a single mismatch counter make a fixed-window frequency check O(1) per slide?

## The problem shape Some fixed-window questions are not about a numeric aggregate but about *membership up to reordering*: does this window contain exactly the same symbols, with the same multiplicities, as some target? A concrete original setting: an intrusion detector reads a keystroke log and must flag any 8-keystroke run whose keys are exactly the 8 keys of a privileged access code, in any order, because the operator may type them scrambled. Because reordering is allowed, the identity of a window is its *frequency fingerprint*: a mapping from symbol to count. Two windows of equal length match the target if and only if their fingerprints are equal as multisets. And because the window has the same length as the target, equality of fingerprints is the whole test — there is no room for extra symbols to hide. ## The naive per-slide cost The direct implementation keeps a count table for the window, updates two entries per slide, and then compares the whole table with the target table. That comparison walks the alphabet: `O(sigma)` per position, `O(n · sigma)` overall. For a small alphabet this is cheap in practice and perfectly acceptable to say out loud — but it is wasteful in an obvious way. Between two adjacent positions, *at most two* table entries changed. Re-reading every entry to discover that fact is the same mistake as recomputing a window sum from scratch, one level up. ## The mismatch counter Maintain a single integer alongside the table: > `bad` = the number of symbols s for which `count[s] != need[s]` where `need[s]` is the target multiplicity and defaults to 0 for symbols the target does not contain. This definition deliberately ranges over *all* symbols, not just the target's, which is what makes intruding symbols count automatically: a symbol with `need == 0` is fine while its window count is 0 and becomes a mismatch the instant it appears. The window matches exactly when `bad == 0`. Updating it is local. For each of the two touched symbols, ask *was it in agreement before the change* and *is it in agreement after*, and move `bad` by the delta: - agreed before, disagrees after: `bad` goes up by one; - disagreed before, agrees after: `bad` goes down by one; - otherwise unchanged. Two symbols, two constant-time checks each, and the match test is a single comparison against zero. Cost per slide is independent of the alphabet **and** of the window length. ## Initialisation Start with an empty window and `count` all zeros, so `bad` equals the number of distinct symbols the target actually requires. Then feed the first w symbols through exactly the same enter-side update. When the window is full, `bad` is already correct and every subsequent step is a single slide. Writing initialisation as "the same update, run w times" rather than as separate code is what keeps the two paths from drifting apart — a very common source of a bug that only shows up on the first window. ## The edge cases that get probed **Entering and leaving symbol coincide.** If the symbol arriving equals the symbol departing, the count returns to where it started. Running the enter-update and the leave-update in sequence handles this correctly on its own: the first pushes the count off and possibly increments `bad`, the second pulls it back and decrements it again. You do not need a special case, but you should be able to say why not. **Symbols outside the target.** These are exactly why `bad` is defined over the union rather than over the target's symbols only. A version that tallies only "how many target symbols are satisfied" will happily report a match for a window that satisfies all of them plus contains an extra intruder — which cannot happen when the window length equals the target length, but *does* happen the moment someone reuses the code for a longer window. Knowing which invariant is load-bearing is the difference between code that works and code that works by accident. **Alphabet representation.** For a small fixed alphabet a plain array indexed by symbol is the natural table; for an open alphabet you need an associative structure, and the per-slide cost becomes constant *expected* rather than constant worst-case, since hashed lookups degrade under collisions. Say "expected O(1)" and you have already answered the follow-up. ## Why the fixed size matters All of this is easy precisely because the window length never changes: exactly one symbol enters and exactly one leaves, so the number of table entries touched per step is bounded by two, and window validity is a pure equality test with no shrinking loop. A window that grows and shrinks needs a different invariant — the counter there answers "is the window at least good enough", not "is it exactly equal" — which is why the two cases are worth separating in your head before you start writing.