Sliding Window III — With Counts

Review boundary and corrected contracts

The matches counter shown here tracks exact equality only for required character types; irrelevant characters must not alter that particular invariant. Other bookkeeping conventions need their own proof and are not automatically wrong. Empty-target behavior is explicitly defined. Minimum-window coverage means every required multiplicity is met, not merely that each character appears.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own count-driven windows: a need-map plus one formed integer that tells you the window is valid in O(1), the technique behind Minimum Window Substring.

Series: LeetCode — From Basics to Production-Ready · Session 11 / 65 · Phase 1 · Core patterns

Prerequisites. L10 (variable-size window) — this is the count-tracking upgrade of it. You need collections.Counter/defaultdict and the grow-right/shrink-left skeleton from L10.

What this pattern IS

L10's windows were valid by a simple test: no repeats (a set), sum ≥ target (an integer). But some windows are valid only when they contain enough of each of several characters — "does this window contain every letter of t with at least the required multiplicity?"

A baseline scans required counts on each step, checking window[c] >= need[c] for coverage. Exact Counter equality is a different predicate for permutations: a covering window may contain extra characters or extra copies. Scanning A required keys costs O(A) per check; maintaining crossings avoids that repeated scan, though it is not guaranteed faster for every small input.

The count technique compresses that whole comparison into one integer. You keep:

• need — a Counter of how many of each character the window must contain.
• have — the number of distinct required character types currently meeting their multiplicities, not the total number of matched occurrences.

When have == len(need), every required character is satisfied — the window is valid — and you learned that in O(1), by watching a single counter tick up and down. That's the entire trick, and it's what turns Minimum Window Substring from scary into routine.

A checklist with a completed-count

Real: A shipping order needs 3 red, 2 blue, 1 green. Instead of re-reading the whole checklist each time an item arrives, you keep one number: how many line-items are fully satisfied. When that number equals the number of line-items, the order is complete.

need = {'r':3,'b':2,'g':1}; when window[c] == need[c], have += 1; valid when have == len(need).

First principles

Question: Why can 'window contains enough of every required char' be tested in O(1) instead of comparing two maps?

Premise: Validity = for every required char c, window_count[c] ≥ need[c]. That's a conjunction over all required chars.

Because: The window is valid exactly when EVERY line-item is met — an AND across the need-map keys.

Premise: A conjunction of booleans equals 'number of true clauses == total clauses'.

Because: All clauses true ⇔ the count of true clauses reaches the total count.

Premise: That count changes by at most 1 when a single character enters or leaves the window.

Because: Adding one char can push exactly one line-item from unmet to met; removing one can push exactly one from met to unmet.

Premise: So maintain 'have = number of satisfied line-items' incrementally, adjusting by ±1 on each add/remove.

Because: You never rescan the map — you only react to the one char that moved across the window edge.

Premise: Validity is then the O(1) test have == len(need).

Because: One integer comparison replaces an O(alphabet) map comparison.

Conclusion: Track a single 'satisfied line-items' counter; the window is valid iff it equals the number of required characters.

The templates

Template A — minimum window covering a target multiset

from collections import Counter
 
def min_window(s, t):
    if not t or not s:
        return ""
    need = Counter(t)              # required counts
    missing = len(need)           # number of DISTINCT chars not yet satisfied
    window = Counter()
    left = 0
    best = (float('inf'), 0, 0)   # (length, l, r)
    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            missing -= 1          # this char just became fully satisfied
        while missing == 0:       # window is valid -> shrink to minimise
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            lc = s[left]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                missing += 1      # dropped below requirement -> no longer satisfied
            left += 1
    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

On addition, a required count crosses from unmet to met exactly when it becomes equal to its requirement. In this function, removal happens only while all requirements were met, so after decrement < need[lc] identifies the single met-to-unmet crossing and immediately ends shrinking. That < test is not a general removal rule for an already-invalid window: repeated removal below threshold would overcount missing types. In a general update routine, compare the before/after threshold status instead.

For each right endpoint the loop records covering candidates while discarding starts; once a start has supplied a covering candidate, extending its end only makes it longer, so that start cannot yield a better future answer. This justifies shrinking separately from the O(n) pointer-move bound. The strict shorter-than update preserves the earliest start among equal-length minimum windows.

Template B — fixed window with a single matches counter (anagram / permutation)

from collections import Counter
 
def contains_permutation(s1, s2):
    if not s1:
        return True
    need = Counter(s1)
    k = len(s1)
    window = Counter()
    matches = 0
    for right, ch in enumerate(s2):
        if ch in need and window[ch] == need[ch]:
            matches -= 1
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            matches += 1
        if right >= k:
            old = s2[right - k]
            if old in need and window[old] == need[old]:
                matches -= 1
            window[old] -= 1
            if old in need and window[old] == need[old]:
                matches += 1
        if right >= k - 1 and matches == len(need):
            return True
    return False
 

Here matches counts exact equality for required characters only (permutation needs equal counts, not "at least"). The before-update and after-update checks subtract the old equality contribution and add the new one; an irrelevant character must never change matches. A full window has k characters and the target requirements sum to k, so matching every required multiplicity leaves no room for extra irrelevant characters. This implication requires the full-width check. Empty s1 returns True by the stated empty-pattern convention. Both overshoot and undershoot can flip a required character’s equality contribution. Think of the gauge below as a count of completed checklist rows, then decide what completes a row. Minimum Window keeps a row complete when extra copies arrive; the permutation template switches it off again on overshoot. The picture's enter/leave rules describe the first case — use the equality-crossing guards above for the second.

Mental model

Name: One counter, not a whole map

Picture: A dashboard with a single gauge: 'requirements met'. Each character crossing the window edge nudges the gauge by at most ±1. Window valid ⇔ gauge is full. Never re-read the whole map.

• Keep need (targets) and window (live counts).

• On entering char: if it just hit its target, satisfied += 1.

• On leaving a required char: decrease satisfied only on a met-to-unmet crossing, not on every removal below target.

• Valid ⇔ satisfied == number of distinct required chars.

Trigger: 'window/substring containing all of ...', 'anagram/permutation', 'at least/exactly the required count of each character'.

Memory / mnemonic

The engine is four guarded lines. Peg them as "UP on equal, DOWN on below."

• Entering a char: it can only raise your window count, so the only interesting crossing is window[c] == need[c] → satisfied UP.
• Leaving a required char: a before-count equal to need becomes below need after removal, so satisfied goes DOWN. The shorter < need condition in min_window is safe because its shrink loop begins valid and stops at the first failed requirement.

For the exact-match (permutation) variant, add the overshoot beat: "equal is a match, one-over breaks it." == need[c] gains a match; == need[c] + 1 loses it.

The recall cue is "need-map + one integer." A full-map scan remains a useful small-input baseline or independent oracle; the single integer is an optimization with a state invariant to verify.

The trap

Myth: To check window validity you compare the window's Counter to the need Counter each step.

Truth: That map comparison is O(alphabet) per step and unnecessary. Maintain a single satisfied/missing integer that moves by ±1 as chars cross the edges.

Why: Only one character enters or leaves per step, so at most one requirement changes status — a full comparison redoes work for every other unchanged key.

Test: Compare the optimized result against brute-force coverage on small strings with repeated target letters, irrelevant symbols, surplus required letters and an empty target. Count full-map inspections versus threshold updates separately from timing; no judge result or universal speed ratio is implied.

What reviewers actually ask

These practice problems distinguish coverage, exact equality and number of distinct types; no employer-frequency or pass/fail claim is established here.

• Minimum Window Substring (76) · Hard · Practice selection. — probes: the need-map + satisfied-counter with correct shrink; the definitive test of this pattern. Follow-up: what if there are multiple minimum windows, or the input streams?
• Find All Anagrams in a String (438) · Medium · Practice selection. — probes: fixed window with a matches counter; return all start indices. Follow-up: count matches only, or a huge alphabet.
• Permutation in String (567) · Medium · Practice selection. — probes: exact-count fixed window (overshoot breaks a match). Follow-up: return the first index, or handle repeats in s1.
• Longest Substring with At Most K Distinct Characters (340) · Medium · Practice selection. — probes: distinct-count via len(window) as the validity signal. Follow-up: exactly K distinct (subtract two at-most bounds).
• Substring with Concatenation of All Words (30) · Hard · Practice selection. — probes: word-level count window with multiple offsets. Follow-up: variable word lengths.
• Longest Repeating Character Replacement (424) · Medium · Practice selection. — probes: validity via maxfreq (a count-derived signal). Follow-up: why maxfreq needn't decrease.

For each implementation, state what the integer counts, why its updates preserve that meaning, and which map keys contribute. A small update count alone does not establish correctness.

Worked solutions

1. Minimum Window Substring (76)

Plain words: for strings s and t, return the earliest shortest substring covering every required code-point multiplicity, or "" if none exists. Empty t returns ""; minWindowStart below returns 0 for that empty-target convention and -1 when a nonempty target cannot be covered. Matching is case-sensitive and does not normalize Unicode or group grapheme clusters.

Brute force: there are O(n²) candidate substrings; scanning A required counts per candidate adds O(n²A) checks if counts are maintained per starting index. Rebuilding each candidate’s counts also scans its length and can add O(n³) character work. Insight: variable window (L10) + the count engine — grow to cover t, then shrink to minimise, testing validity with the missing integer.

from collections import Counter
 
def minWindow(s, t):
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(need)               # distinct chars still under their requirement
    window = Counter()
    left = 0
    best = (float('inf'), 0, 0)
    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            missing -= 1              # ch is now fully covered
        while missing == 0:          # valid -> record and shrink
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            lc = s[left]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                missing += 1         # dropped below -> window no longer valid
            left += 1
    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

Complexity: expected O(|s|+|t|) time under bounded-cost character hashing, plus the O(answer length) final slice; auxiliary maps use O(A) space for distinct code points encountered in s or t, including zero-count keys retained by this implementation. The returned substring adds its own storage. For an irreversible stream, expired characters must be buffered to update counts, and previously best output text must remain retrievable after its window expires. Saving only indices is insufficient without backing storage; copying every improving candidate naively can add quadratic total copy work. This indexed-string implementation is not a complete bounded-memory streaming solution.

Goal: Return the START INDEX of the minimum window instead of the substring.

Hint: best already stores (length, left, right); return best[1] when found, else -1.

def minWindowStart(s, t):
    if not t:
        return 0
    need = Counter(t); missing = len(need); window = Counter()
    left = 0; best = (float('inf'), -1)
    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            missing -= 1
        while missing == 0:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left)
            lc = s[left]; window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                missing += 1
            left += 1
    return best[1]

2. Permutation in String (567)

Plain words: given s1 and s2, return True if any substring of s2 is a permutation of s1 (a window of length len(s1) with identical character counts).

Insight: fixed window of size len(s1); maintain a matches counter tracking how many characters have exactly the required count. Valid when matches == len(need).

from collections import Counter
 
def checkInclusion(s1, s2):
    if not s1:
        return True
    need = Counter(s1)
    k = len(s1)
    window = Counter()
    matches = 0
    for right, ch in enumerate(s2):
        if ch in need and window[ch] == need[ch]:
            matches -= 1
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            matches += 1
        if right >= k:
            old = s2[right - k]
            if old in need and window[old] == need[old]:
                matches -= 1
            window[old] -= 1
            if old in need and window[old] == need[old]:
                matches += 1
        if right >= k - 1 and matches == len(need):
            return True
    return False
 

Complexity: expected O(|s1|+|s2|) time, including target construction, and O(A) map space for distinct code points encountered across the two strings. The maps retain zero entries; O(26) applies only if both strings are restricted to lowercase ASCII. To return the first start, return right-k+1 on a match, 0 for the empty-pattern convention and -1 on failure.

3. Longest Substring with At Most K Distinct Characters (340)

Plain words: for an integer K>=0, return the maximum length of a substring with at most K distinct code points. Empty s or K=0 returns 0. Negative K is outside this length function’s contract.

Insight: the validity signal is simply len(window) — the number of distinct chars currently in the window. Grow right; while more than K distinct, shrink left (deleting zero-count keys keeps len(window) honest).

from collections import defaultdict
 
def lengthOfLongestSubstringKDistinct(s, k):
    if k == 0:
        return 0
    window = defaultdict(int)
    left = 0
    best = 0
    for right, ch in enumerate(s):
        window[ch] += 1
        while len(window) > k:        # too many distinct -> shrink
            lc = s[left]
            window[lc] -= 1
            if window[lc] == 0:
                del window[lc]         # keep len(window) == true distinct count
            left += 1
        best = max(best, right - left + 1)
    return best

Complexity: expected O(n) time with bounded-cost hashes and O(min(n,K+1)) transient map storage; after shrinking, at most K keys remain. This function returns a maximum length, so subtracting two calls does not count exactly-K substrings. For example, on "aba", longest-at-most-2 minus longest-at-most-1 is 3−1=2, but there are 3 substrings with exactly two distinct characters.

The subtraction identity needs counts, using a different accumulator:

def count_at_most_k_distinct(s, k):
    if k < 0:
        return 0
    counts = {}
    left = total = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > k:
            old = s[left]
            counts[old] -= 1
            if counts[old] == 0:
                del counts[old]
            left += 1
        total += right - left + 1
    return total
 
def count_exactly_k_distinct(s, k):
    if k < 0:
        raise ValueError("k must be nonnegative")
    return count_at_most_k_distinct(s, k) - count_at_most_k_distinct(s, k - 1)

After shrinking, every start from left through right yields a valid ending range, and every earlier start is invalid. Thus right-left+1 counts all valid nonempty ranges ending here exactly once. At-most-K ranges split into those with fewer than K types and exactly K types, proving the difference identity for counts. For K=0 both counts are zero. Each pass uses expected O(n) time and bounded live-key storage, not a list of all substrings.

Tradeoff

Decision: Test whether a window meets a multi-character count requirement.

Name: Scan required counts for coverage, or compare full Counters for permutation

Gain: Straightforward independent baseline when its predicate matches the requested coverage or equality contract.

Cost: O(A) checks per step for A relevant keys; runtime depends on alphabet, data and implementation.

Pick: Small alphabet, short strings, or a first correct-but-slow pass.

Name: Single satisfied/missing counter

Gain: O(1) validity check; the expected optimal for Minimum Window Substring.

Cost: Fiddly ± bookkeeping at the exact ==/< crossings; easy to introduce an off-by-one.

Pick: Whenever performance matters or a reviewer asks for O(1) per step.

Name: Array-of-256 counts + matches

Gain: Direct indexing without hash lookup; it may reduce overhead for an explicitly bounded alphabet, but is not universally fastest.

Cost: Assumes a specified character-to-index mapping; arbitrary Unicode code points do not fit a 256-entry table.

Pick: Competitive settings or when the alphabet is known and small (ASCII).

Verdict: Choose the simplest correct predicate and representation that meets measured or stated requirements. Keep the baseline as a test oracle when optimizing; threshold bookkeeping adds correctness obligations.

Where this shows up

As a conceptual example, a monitoring query can require minimum counts of several event types in a time interval. The satisfied-type counter handles that predicate, while event ordering, expiration, late data, atomic updates and memory limits need separate mechanisms. Scanning an A/C/G/T sequence for fixed-size regions of a required composition is a direct finite-alphabet example; ambiguity symbols or biological sequence semantics require an expanded contract. Neither analogy is an executed production or bioinformatics system.

Checkpoint

You can now…

• Explain why a multi-char validity condition compresses to a single integer.

• Write the need-map + missing-counter Minimum Window Substring from scratch.

• Get the ==/< crossings right so the counter moves by exactly ±1.

• Use a matches counter for exact-count anagram/permutation windows.

• Use len(window) as the validity signal for K-distinct problems.

• Choose between full-map comparison and the O(1) counter based on constraints.

Quiz

Self-check (answer follows each question).

Recall check

Q: What single integer replaces comparing two frequency maps, and what does it count?

A: A satisfied/missing counter — the number of required characters whose window count currently meets (or fails) their requirement.

Q: When a character ENTERS the window, what's the exact condition that increments 'satisfied'?

A: For a required character, the updated count equals need[ch], crossing from below to met. Check membership in need; irrelevant characters cannot satisfy a required row.

Q: When a character LEAVES, what condition decrements 'satisfied'?

A: A required character crosses from a before-count equal to need[ch] to below it. The displayed minimum-window loop can use the post-removal < test because it removes only from a valid window and stops on the first deficiency. Do not decrement repeatedly while already below the threshold.

Q: In Permutation in String, why does an overshoot (window[ch] == need[ch] + 1) DECREMENT matches?

A: Permutation needs EXACT counts; overshooting means that character no longer matches exactly, so it stops being a satisfied line-item.

Q: In K-distinct, what quantity is the validity signal and why must you delete zero-count keys?

A: len(window) is the number of distinct chars; deleting zero-count keys keeps len(window) equal to the true distinct count so the > k test is correct.

Q: ★ Stretch: how do you compute 'exactly K distinct' from an 'at most K distinct' subroutine, and why does it work?

A: Use count_at_most_k_distinct, which accumulates right-left+1 at each endpoint, then subtract its results for K and K−1. Do not subtract maximum lengths from lengthOfLongestSubstringKDistinct. The counted at-most-K ranges partition into fewer-than-K and exactly-K ranges, so the difference counts exactly K.

Stretch: true

Practice queue

+7d / +21d are optional elapsed-day practice reminders.

• Find All Anagrams in a String (438) — Medium · matches-counter warm-up · +7d anchor.
• Permutation in String (567) — Medium · exact-count window.
• Longest Substring with At Most K Distinct Characters (340) — Medium · distinct-count signal.
• Minimum Window Substring (76) — Hard · the boss · +21d anchor.
• Longest Repeating Character Replacement (424) — Medium · count-derived validity.
• Subarrays with K Different Integers (992) — Hard · atMost(K) − atMost(K−1).
• Substring with Concatenation of All Words (30) — Hard · word-level count window.

Corrective source notes

• collections — Container datatypes — Python 3.14.8 documentation — Counter equality in Python 3.10+ treats missing keys as zero counts. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.