L11 · Sliding Window III — With Counts

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

Watch first

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?"

The naive validity test rebuilds or compares a whole frequency map on every step. Comparing two maps is O(alphabet); doing it inside a window loop makes the constant fat and, for large alphabets, genuinely slow.

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 — how many characters currently meet their required count.

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.

First principles

The templates

Template A — minimum window covering a target multiset

from collections import Counter
 
def min_window(s, t):
    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]

The two if ch in need and window[ch] == need[ch] / < need[ch] lines are the whole O(1) validity engine. Note the strict == on the way up (fires exactly once, when you first hit the requirement) and < on the way down (fires exactly once, when you first drop below it).

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

from collections import Counter
 
def contains_permutation(s1, s2):
    need = Counter(s1)
    k = len(s1)
    window = Counter()
    matches = 0                   # how many chars have window[c] == need[c]
    for right, ch in enumerate(s2):
        window[ch] += 1
        if window[ch] == need[ch]:
            matches += 1
        elif window[ch] == need[ch] + 1:
            matches -= 1          # just overshot -> no longer a match
        if right >= k:            # drop the char leaving the fixed window
            lc = s2[right - k]
            if window[lc] == need[lc]:
                matches -= 1
            elif window[lc] == need[lc] + 1:
                matches += 1      # came back down to a match
            window[lc] -= 1
        if matches == len(need):  # every char count matches exactly
            return True
    return False

Here matches tracks exact equality (permutation needs equal counts, not "at least"), so both overshoot and undershoot flip it.

Mental model

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 char: it can only lower the count, so the interesting crossing is window[c] < need[c] → satisfied DOWN.

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 for the whole family: "need-map + one integer." If your validity check loops over the map, you've forgotten the integer.

The trap

What interviewers actually ask

Count-window problems are a favourite because Minimum Window Substring is a genuine filter and its lighter cousins are extremely common.

• Minimum Window Substring (76) · Hard · Meta, Amazon, Uber — 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 · Meta, Amazon — 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 · Meta, Amazon — 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 · Amazon, Meta — 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 · Amazon — probes: word-level count window with multiple offsets. Follow-up: variable word lengths.
• Longest Repeating Character Replacement (424) · Medium · Google, Amazon — probes: validity via maxfreq (a count-derived signal). Follow-up: why maxfreq needn't decrease.

Universal probe: "don't rescan the map — keep it O(1) per step." Saying and coding that is the pass.

Worked solutions

1. Minimum Window Substring (76)

Plain words: given strings s and t, return the shortest substring of s that contains every character of t including duplicates, or "" if none exists.

Brute force: check every substring for coverage — O(n^2) windows times O(alphabet) coverage = far too slow. 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: O(|s| + |t|) time, O(alphabet) memory. Follow-up — "streaming s": the algorithm is already single-pass over s with two forward pointers, so it streams as long as you can buffer the current window.

def minWindowStart(s, t):
    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 len(s1) > len(s2):
        return False
    need = Counter(s1)
    k = len(s1)
    window = Counter()
    matches = 0
    for right, ch in enumerate(s2):
        window[ch] += 1
        if window[ch] == need[ch]:
            matches += 1
        elif window[ch] == need[ch] + 1:
            matches -= 1              # overshot the exact count
        if right >= k:
            lc = s2[right - k]
            if window[lc] == need[lc]:
                matches -= 1
            elif window[lc] == need[lc] + 1:
                matches += 1
            window[lc] -= 1
        if matches == len(need):
            return True
    return False

Complexity: O(|s2|) time, O(26) memory. Follow-up — "return the first start index": return right - k + 1 at the match instead of True.

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

Plain words: return the length of the longest substring of s containing at most K distinct characters.

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: O(n) time, O(k) memory. Follow-up — "exactly K distinct": compute atMost(K) − atMost(K−1) using this as a subroutine.

Tradeoff

Where this shows up

Count-driven windows appear in log and stream monitoring: "alert when, within any rolling window, we've seen at least N of each critical error type" is exactly a need-map plus a satisfied-counter over a sliding time window. Bioinformatics uses the same fixed-window count-match to scan a genome for regions matching a required nucleotide composition — a direct analogue of Find All Anagrams over a 4-letter alphabet.

Checkpoint

Quiz

Practice queue

+7d / +21d mark spaced-repetition anchors.

• 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.