Sliding WindowAlgorithmaka anagram window, character-count window, need/have window, minimum window template

Sliding Window with Frequency Map

Slide a window over a string while a hash map tracks character counts and a "formed" counter says how many required characters are satisfied — the engine behind anagram search and minimum window substring.

▶ VisualizePattern: Sliding WindowPractice (4)
Progress

Overview

Many substring problems ask whether a window contains a required multiset of characters: exactly the letters of p (anagram), or at least the letters of t (Minimum Window Substring). Checking a window by comparing two frequency tables costs O(Σ) per window, where Σ is the alphabet size; over n windows that is O(n·Σ), and with a naive recount it would be O(n·m).

The frequency-window technique keeps a need map (counts required from the pattern) and a have/window map (counts currently inside the window), plus a single integer formed: how many *distinct* characters currently meet their required count. Every add or remove touches one character and can change formed by at most one, so the "is this window valid?" question becomes formed == required in O(1). Combined with a fixed window (anagrams) or a variable window (minimum window substring), this gives O(n + m) overall.

stringsubstringhash mapfrequencyanagramO(n)

Intuition

A mental model before the formal terms.

You are a shopkeeper who needs a specific list of items — 2 apples, 1 banana. As customers file through a corridor (the window), you keep a checklist: each item type is either "fulfilled" or "short". Rather than recounting the whole corridor every time someone enters or leaves, you only update the single line for that person's item and adjust the count of fulfilled lines. When *all* lines are fulfilled, the corridor is a valid window; then you start letting people leave from the front to see how short the corridor can be while staying fulfilled.

How it works

  1. Build need: need[c] = number of times c occurs in the pattern t. Let required = |need|, the number of distinct characters.
  2. Initialize window (empty map), formed = 0, l = 0.
  3. For each r: let c = s[r]. Increment window[c]. If c is in need and window[c] == need[c], increment formed — this character just became satisfied.
  4. Fixed-width variant (anagrams): if the window exceeds |t|, remove s[l] (decrementing formed if that character drops below its requirement) and l++. When the width is exactly |t| and formed == required, record l as a match.
  5. Variable-width variant (minimum window): while formed == required, the window is valid — record it if it is the shortest so far, then remove s[l] (decrementing formed if window[c] falls below need[c]) and l++ to try a shorter one.
  6. Return the collected matches or the best [l, r] range.

Why it works

Invariant: window is exactly the character multiset of s[l..r], and formed equals the number of characters c with window[c] ≥ need[c]. Both are maintained incrementally: adding c can only push window[c] from need[c] − 1 to need[c] (formed++), and removing c can only push it from need[c] to need[c] − 1 (formed−−). Any other change leaves the satisfied/unsatisfied status of c unchanged, and no other character is affected.

formed == required is therefore equivalent to "the window contains at least every required character in sufficient quantity". For a window of width exactly |t|, "at least" forces "exactly", which is the anagram condition.

The variable-width shrink is safe by the same monotonicity argument as Sliding Window (Variable Size): containment of a multiset is monotone under inclusion. Once s[l..r] is valid, every shorter window ending at r with a larger l is tried; once shrinking makes it invalid, no window starting before the new l and ending at any r' > r can be the *minimum*, because it strictly contains a window that was already recorded.

Each index enters and leaves the window once, and each entry/exit is O(1) with a hash map (or an array of size Σ), giving O(n + m) total.

Recognition

How to tell a problem wants this.

  • "Find all anagrams of p in s", "does s2 contain a permutation of s1", "substring with the same character counts".
  • "Minimum window substring that contains all characters of t", "smallest substring containing all", "contains every character at least as many times as".
  • "Substring with concatenation of all words" — the same idea with word-sized tokens instead of characters.
  • The pattern has a small alphabet (a–z, ASCII) and the solution must be linear: |s|, |t| ≤ 10^5.
  • You start writing sorted(window) == sorted(p) inside a loop — that is the O(n·m log m) version this technique replaces.
“contiguous subarray” → Sliding Window“have you seen this before” → Hashing

Interactive visualization

Play, step, change the input. ← → and space work too.

a
a
0
a
1
b
2
a
3
c
4
b
5
e
6
b
7
e
8
b
9
e
10
freq (char:count)
1/28Longest substring with at most k=3 distinct characters. A frequency map tracks what is inside the window so "how many distinct" is just the map's size.
Current windowEntering (r)Shrunk awayBest window
PseudocodeLearn Sliding Window with Frequency Map →
1l = 0, best = 0, freq = {}
2for r in 0 .. n-1:
3  freq[s[r]] += 1
4  while len(freq) > k:
5    freq[s[l]] -= 1; if freq[s[l]] == 0: delete freq[s[l]]
6    l += 1
7  best = max(best, r - l + 1)
8return best
Variables
l0
best0
k3
distinct0
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(Σ)
Speed

Pseudocode

1need = counts(t); required = |need|
2window = {}, formed = 0, l = 0, best = (inf, -1, -1)
3for r in 0..n-1:
4  c = s[r]; window[c] += 1
5  if c in need and window[c] == need[c]: formed += 1
6  while formed == required:            # window [l, r] is valid
7    if r - l + 1 < best.len: best = (r - l + 1, l, r)
8    d = s[l]; window[d] -= 1
9    if d in need and window[d] < need[d]: formed -= 1
10    l = l + 1
11return s[best.l .. best.r] or ""

Implementations

1# Minimum Window Substring: shortest substring of s containing every character of t
2from collections import Counter, defaultdict
3 
4 
5def min_window(s: str, t: str) -> str:
6    if not s or not t:
7        return ""
81 · Build the need table and count distinct required characters
9    need = Counter(t)
10    required = len(need)
112 · Window state: formed = distinct characters currently satisfied
12    window: defaultdict[str, int] = defaultdict(int)
13    formed = 0
14    l = 0
15    best_len, best_l = float("inf"), 0
163 · Expand: add s[r] and update formed when a character becomes satisfied
17    for r, c in enumerate(s):
18        window[c] += 1
19        if c in need and window[c] == need[c]:
20            formed += 1
214 · Shrink while valid: record the window, then drop s[l]
22        while formed == required:
23            if r - l + 1 < best_len:
24                best_len, best_l = r - l + 1, l
25            d = s[l]
26            window[d] -= 1
27            if d in need and window[d] < need[d]:
28                formed -= 1
29            l += 1
305 · Return the shortest window found (or empty)
31    return "" if best_len == float("inf") else s[best_l : best_l + int(best_len)]
Walkthrough
  1. Counter(t) builds the need table in one call; len(need) is the number of distinct required characters.
  2. defaultdict(int) for the window means window[c] += 1 works without a membership check.
  3. enumerate(s) gives (r, c) directly — no s[r] indexing for the entering character.
  4. formed is bumped only when window[c] == need[c] right after the increment.
  5. The result slice s[best_l : best_l + best_len] copies the substring once at the end.
Complexity (this implementation)
time O(n + m) · space O(Σ)

The final slice copies O(best_len) characters — unavoidable in Python since strings are immutable, but done once.

Language notes
  • Counter supports need - window and not (need - window) as a validity test, but that is O(Σ) per check; the formed counter keeps it O(1).
  • defaultdict(int) vs Counter for the window: both work; Counter adds most_common and arithmetic, defaultdict is marginally faster for plain increments.
  • float("inf") is the idiomatic sentinel; int(best_len) converts back before slicing because slice bounds must be integers.
Common mistakes in this language
  • Using a plain dict and forgetting window.get(c, 0) on the first increment (KeyError).
  • Testing validity with Counter(s[l:r+1]) >= need inside the loop — O(window) per step.
  • Slicing with s[best_l:best_r] when best_r was stored inclusive.
Language differences that matter here
  • Frequency table choice: C++ std::array<int,128> (or <int,26>) is fastest for ASCII, unordered_map for wide alphabets; JS/TS Map (or Int32Array(128) for speed); Python Counter for need and defaultdict(int) for window.
  • Character iteration: Python and JS for...of iterate code points, but JS s[r] indexes UTF-16 code units; C++ std::string is bytes — signed char must be cast to unsigned char before indexing a table.
  • Substring extraction: C++ substr(start, length), JS/TS slice(start, end), Python s[start:end] — mixing the length/end conventions is a classic off-by-one.
  • Sentinel for "no window": C++ INT_MAX (exact), JS/TS/Python Infinity / float("inf") (a float, needs conversion before use as an index in Python).

Complexity

Best
O(n + m)
Average
O(n + m)
Worst
O(n + m)
Space
O(Σ)

n = |s|, m = |t|, Σ = alphabet size. With a fixed-size int array for ASCII the constant is tiny; a hash map handles Unicode.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • The window must contain (exactly or at least) a required multiset of characters or tokens.
  • Anagram / permutation-in-string search with a fixed-width window.
  • Minimum window containing all of t with a variable-width window.
  • Any "count of distinct satisfied requirements" check that must be O(1) per step.
Avoid it when
  • The condition is about order, not counts (find t as a substring, not an anagram) — use Knuth–Morris–Pratt (KMP), Z-Algorithm, or Rabin–Karp.
  • The requirement is not monotone under inclusion (e.g. "exactly these characters and no others" over a variable width) — reformulate or enumerate.
  • Very large alphabets where comparing two maps once per window is fine because n is tiny.
  • Subsequence containment ("is t a subsequence of s") — a single greedy pointer suffices.

Alternatives

Sliding Window (Fixed Size)Sliding Window (Variable Size)Hash MapRabin–KarpKnuth–Morris–Pratt (KMP)

Common mistakes

  • Incrementing formed on every add of a needed character instead of only when window[c] becomes equal to need[c] — overcounts when a character appears more than required.
  • Decrementing formed when window[c] drops from need[c] + 1 to need[c] — that character is still satisfied.
  • In the anagram variant, comparing formed == required before the window has reached width |p|.
  • Off-by-one in the outgoing index: s[r − m] leaves when r ≥ m, not s[r − m + 1].
  • Returning the last valid window instead of the shortest, or slicing with [bestL, bestR) when bestR is inclusive.
  • Treating t as a set (losing multiplicity) — t = "AAB" needs two As.

Interview patterns

  • Minimum Window Substring — the canonical need/formed template.
  • Find All Anagrams in a String and Permutation in String — fixed width plus counts.
  • Substring with Concatenation of All Words — tokens are words; run the window once per offset 0..wordLen−1.
  • Longest Substring with At Most K Distinct — the map size is the constraint; see Sliding Window (Variable Size).
  • Group Anagrams uses the same frequency signature idea but as a hash key rather than a window.
  • Smallest range covering elements from k lists — same "formed" counter over list ids with a heap.
Interview questions on this
Mock interviews

Example problems

Group AnagramsmediumLongest Substring Without Repeating CharactersmediumMinimum Window SubstringhardPermutation in Stringmedium