Window with a need-counter

32 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Does the string eidbaooo contain a rearrangement of ab somewhere inside it, as a block of consecutive letters? By hand you would look at every pair of neighbouring letters, ei, id, db, ba, ao, oo, oo, and ask whether the pair uses exactly the letters a and b. "ba" does, so yes.

For a pattern of length k and a text of length n that is n − k + 1 windows, each needing a comparison of two letter-count tables, which is 26 entries, or k if you sort the window. For a text of a million letters and a pattern of a thousand that is about a billion letter operations. The waste is the full recount at every window when only one letter entered and one left.

Build the structure, one piece at a time

Piece one: a need table: how many of each letter the pattern requires. For ab it is {a: 1, b: 1}. Think of it as a shopping list.

Piece two: a fixed-size window of k letters over the text. When a letter enters the window, cross it off the list: need[letter] −= 1. When a letter leaves, put it back: need[letter] += 1. Letters not on the list simply go negative and positive again; they are never required.

Piece three, the counter that avoids rescanning the table: missing, the number of letters still short. It starts at the pattern length k. When a letter enters and its need was positive before the decrement, missing −= 1 (we filled a real requirement). When a letter leaves and its need becomes positive after the increment, missing += 1 (we uncovered a requirement). The window matches exactly when missing = 0.

Wait: in the last row b left the window, so need[b] went back to 1 and missing went back up. The window "ba" is the one before that step: after a enters and before b leaves, need is {a:0, b:0} and missing is 0, a match. In code the check happens after the entering step and before the leaving step for a fixed window, or the leaving step happens only when the window exceeds size k.

Why it is correct

The invariant: need[c] equals (count of c in the pattern) − (count of c in the window), and missing equals the sum of the positive entries of need. Both start true (empty window). An entering letter lowers its need by one; that lowers the positive-sum by one exactly when the need was positive before, which is the rule for missing. A leaving letter raises its need by one; that raises the positive-sum by one exactly when the need is positive afterwards. So the invariant is kept by every step.

Then missing = 0 means no letter is short, and since the window has exactly k letters and the pattern has exactly k letters, no letter can be in surplus either:

Σ_c need[c] = k − k = 0, and no entry is positive ⇒ every entry is 0

So the window's letter counts equal the pattern's, which is the definition of an anagram.

Why it is fast

Each of the n text letters enters once and leaves once, and each event is two or three O(1) updates. The match test is a comparison of missing with zero, not a 26-entry scan. Total O(n + alphabet) time, the alphabet term being the need table's size, and O(alphabet) memory. The billion-operation example becomes a few million.

How to recognise it in an interview

Cues: "contains an anagram/permutation of", "all characters of t (with multiplicity)", "find all start indices where the window is a rearrangement". The giveaway is a requirement stated as a multiset of characters. Say: "I will keep a need table from the pattern and a missing counter, update both as letters enter and leave, and report a match whenever missing is zero."

Permutation in String and Find All Anagrams in a String use a fixed window of the pattern's length. Minimum Window Substring uses the same table and counter with a variable window: grow until missing is zero, then shrink while it stays zero.

02The idea in one line

Track how many required characters are still missing; zero means satisfied.

Reach for it when: Anagram windows, minimum window substring, character budgets.

Cost: O(n + alphabet) time.

03The walk-through, step by step

The video works one example: Permutation in String: 'ab' inside 'eidbaooo'. These are its captions in order, so you can follow without the video or check a step you missed.

1. A need counter per letter; missing = letters still short. Zero missing = match
2. 'e' not needed
3. 'i' not needed
4. 'd' not needed; drop 'e'
5. 'b' needed: need[b] → 0, missing → 1; drop 'i'
6. 'a' needed: need[a] → 0, missing → 0; drop 'd' → missing = 0
7. Window [3..4] = 'ba' is a permutation of 'ab': true
8. Counter updates are O(1) per step: O(n + alphabet)

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sliding Window: Fixed-size window, Longest valid window, Shortest satisfying window, Count windows via at-most(k) trick.