Learn/DSA Patterns
DSA PatternsStringsmedium10 min read

Sliding Window on Strings

A sliding window with a character frequency map finds substrings satisfying frequency constraints in O(n) time. This chapter covers the variable-size window (minimum window substring), the fixed-size window (find all anagrams / permutation match), and the 'at most k distinct characters' family.

#sliding-window#strings#frequency-map#anagram#minimum-window#permutation#beginner#interview
Table of contents

The problem with brute force

You need to find the shortest substring of s that contains every character of pattern t. The brute-force approach checks every possible (start, end) pair and counts characters — O(n² × m) for string length n and pattern length m. Far too slow for n = 100 000.

We already know from Chapter 1.5 that a variable-size sliding window shrinks and grows in O(n) total steps. The new ingredient for strings is a character frequency map that tracks how many required characters are still missing from the current window.

The supermarket restocking story

A real-life story

A store manager has a shopping list of required items (the pattern). A loading dock worker moves along a conveyor belt (the string) picking up items. When the worker has collected every item on the list, the manager shouts "shrink from the left!" — the worker gives back items from the left end of his trolley until the list is no longer satisfied. At that moment, the window is as tight as possible. The worker records the current trolley size and then takes one more step right.

Every expand-then-shrink cycle takes O(1). Over n steps the trolley visits each position at most twice (once when the right pointer adds it, once when the left pointer removes it) → O(n) total.

The one idea to remember

The entire pattern in one sentence

A frequency difference map (need) counts how many more of each character the window still requires; a single integer formed tracks how many distinct characters are fully satisfied — when formed == required, the window is valid and you try to shrink from the left.

Variant 1 — Minimum Window Substring (LC #76)

Find the smallest window in s that contains all characters of t (including duplicates).

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    need   = Counter(t)          # how many of each char we still need
    have   = {}                  # frequency of each char in current window
    required  = len(need)        # number of distinct chars with unmet quota
    formed    = 0                # distinct chars whose quota is currently met

    left = 0
    best_len = float("inf")
    best_start = 0

    for right in range(len(s)):
        c = s[right]
        have[c] = have.get(c, 0) + 1

        # did adding c satisfy c's quota exactly?
        if c in need and have[c] == need[c]:
            formed += 1

        # try to shrink from the left while window is valid
        while formed == required:
            # record if this window is the best so far
            if right - left + 1 < best_len:
                best_len   = right - left + 1
                best_start = left

            # remove leftmost character
            lc = s[left]
            have[lc] -= 1
            if lc in need and have[lc] < need[lc]:
                formed -= 1       # lc's quota is no longer met
            left += 1

    return "" if best_len == float("inf") else s[best_start: best_start + best_len]

Frame-by-frame: s = "ADOBECODEBANC", t = "ABC"

need = {A:1, B:1, C:1}   required = 3   formed = 0

right=0  'A': have={A:1}  formed=1 (A satisfied)
right=1  'D': have={A:1,D:1}  formed=1
right=2  'O': have={..O:1}  formed=1
right=3  'B': have={..B:1}  formed=2 (B satisfied)
right=4  'E': have={..E:1}  formed=2
right=5  'C': have={..C:1}  formed=3 ← window valid!

  Shrink: left=0 'A' → have[A]=0 < need[A]=1 → formed=2; left=1
  Window no longer valid, stop shrinking.
  best = s[0:6] = "ADOBEC", len=6

right=6  'O'  right=7  'D'  right=8  'E': formed still 2
right=9  'B': have[B]=2  (quota already met, formed unchanged)
right=10 'A': have[A]=1 == need[A]=1 → formed=3 ← valid!

  Shrink: left=1 'D' → not in need, just remove. left=2
  left=2 'O' → not in need. left=3
  left=3 'B' → have[B]=1, still ≥ need[B]=1. left=4
  left=4 'E' → not in need. left=5
  left=5 'C' → have[C]=0 < need[C]=1 → formed=2; left=6
  Window "BANC" (s[6..10]) has len 5 < 6 → new best!

right=11 'N'  right=12 'C': have[C]=1 → formed=3

  Shrink: left=6 'O' → not in need. left=7 'D' → not in need. left=8 'E' → not in need.
  left=9 'B' → have[B]=0 < need[B]=1 → formed=2; left=10
  Window "ANC" not valid. Stop.

Answer: "BANC"  ✅

Variant 2 — Find All Anagrams / Permutation in String (fixed-size window)

When the required window size is fixed (= length of pattern), you don't need a formed counter — just compare frequency maps directly or use a deficit counter.

Permutation in String (LC #567)

Does s2 contain any permutation of s1?

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    need = Counter(s1)
    have = Counter(s2[:len(s1)])   # first window
    k    = len(s1)

    if have == need:
        return True

    for i in range(k, len(s2)):
        # add new right character
        have[s2[i]] += 1
        # remove old left character
        old = s2[i - k]
        have[old] -= 1
        if have[old] == 0:
            del have[old]          # keep map clean — avoid false non-equality
        if have == need:
            return True

    return False

Pause & think

Why delete have[old] when its count reaches 0 instead of leaving it as {old: 0}?

Answer

Counter({'a': 1}) == Counter({'a': 1, 'b': 0}) evaluates to False in Python because the second Counter has an extra key. Leaving zero-count keys in have would cause false "not equal" results even when the window truly is an anagram of s1. Deleting the key keeps have clean so the == comparison works correctly.

Find All Anagrams in a String (LC #438)

Same idea, but collect all start indices where an anagram window begins.

def findAnagrams(s: str, p: str) -> list[int]:
    k = len(p)
    if k > len(s):
        return []

    need = Counter(p)
    have = Counter(s[:k])
    result = []
    if have == need:
        result.append(0)

    for i in range(k, len(s)):
        have[s[i]] += 1
        old = s[i - k]
        have[old] -= 1
        if have[old] == 0:
            del have[old]
        if have == need:
            result.append(i - k + 1)

    return result

Variant 3 — At most k distinct characters (variable window)

Find the length of the longest substring with at most k distinct characters.

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    have  = {}
    left  = 0
    best  = 0

    for right in range(len(s)):
        c = s[right]
        have[c] = have.get(c, 0) + 1

        while len(have) > k:          # window has too many distinct chars
            lc = s[left]
            have[lc] -= 1
            if have[lc] == 0:
                del have[lc]
            left += 1

        best = max(best, right - left + 1)

    return best

The while len(have) > k shrink condition replaces the formed == required check from Variant 1 — the map itself tells you whether the constraint is satisfied.

Decision guide: which variant?

Problem shapeWindow sizeValidity signalVariant
Contains all chars of patternVariableformed == requiredMinimum Window
Is a permutation / anagramFixed (= |pattern|)have == needFixed Anagram
At most k distinctVariablelen(have) <= kk-Distinct
Exactly k distinctVariable(at most k) − (at most k−1)Subtract variants

Common traps

Watch out for these

  • Comparing Counter maps with zero-count keys. Always delete a key when its count drops to 0, or have == need will give wrong results.
  • Updating formed too eagerly. Only increment formed when have[c] reaches exactly need[c] (not when it exceeds it). Similarly, only decrement when have[lc] drops below need[lc].
  • Forgetting to handle duplicates in t. If t = "AAB", you need two A's in the window, not just one. The Counter approach handles this automatically — need['A'] = 2.
  • Off-by-one in fixed window start index. When a fixed window match is found at right, the start index is right - k + 1, not right - k.

Complexity

VariantTimeSpace
Minimum Window SubstringO(n + m)O(m) for need map
Fixed Anagram / PermutationO(n + m)O(m) for Counter
At most k distinctO(n)O(k)

Say it like a pro (interview one-liner)

"I'll use a variable sliding window with a frequency difference map. I expand the right pointer one step at a time; when the window is valid (formed == required distinct chars satisfied), I shrink from the left to find the tightest valid window. Each character is added and removed at most once, giving O(n) time."

Remember this forever

Sliding Window on Strings

need     = Counter(t)
have     = {}
formed   = 0
required = len(need)      # distinct chars with quota

for right in range(len(s)):
    c = s[right]; have[c] = have.get(c,0)+1
    if c in need and have[c] == need[c]: formed += 1

    while formed == required:
        update best
        lc = s[left]; have[lc] -= 1
        if lc in need and have[lc] < need[lc]: formed -= 1
        left += 1

Fixed-window anagram: have == need after each slide (delete zero-count keys).

k-distinct: shrink while len(have) > k.

Key trap: only increment/decrement formed at the exact threshold (==), not above/below.

Check yourself

In Minimum Window Substring, why is `formed` incremented only when `have[c] == need[c]` and not when `have[c] > need[c]`?

formed tracks the count of distinct characters whose quota is exactly met for the first time. If have[c] exceeds need[c], the quota was already met at the exact-match step — formed was already incremented then. Incrementing again on every further occurrence would overcount and cause the window to be considered "invalid" (formed > required) prematurely. We only care that each required character appears at least as many times as needed; additional copies are irrelevant to formed.

Why does the minimum window algorithm shrink inside a `while` loop rather than a single `if`?

After the window becomes valid, removing one character from the left may keep the window valid (if that character had excess copies). We should keep shrinking as long as the window remains valid to find the tightest (shortest) possible window before recording the answer. A single if would only try one shrink per right-pointer step and miss tighter windows.

How would you count "exactly k distinct characters" substrings using the at-most-k variant?

exactly_k(s, k) = atMost(s, k) - atMost(s, k-1). Each call runs the at-most variant returning the total count of valid substrings. The difference eliminates substrings with fewer than k distinct characters, leaving exactly k. This is a standard "subtract two sliding window results" technique.

Practice problems

ProblemDifficultyWhat to noticeLink
Minimum Window SubstringHardVariable window; formed/required counterLC #76
Permutation in StringMediumFixed window; have == need; delete zero keysLC #567
Find All Anagrams in a StringMediumFixed window; collect all start indicesLC #438
Longest Substring with At Most K DistinctMediumVariable window; shrink when len(have) > kLC #340
Longest Substring Without Repeating CharactersMediumAt-most-1-distinct variant (each count ≤ 1)LC #3

Next up: KMP Pattern Matching — the O(n) text search algorithm that never backtracks in the text by pre-computing a failure function from the pattern.

PreviousTwo Pointers on StringsNextKMP Algorithm (Pattern Matching)
Back to all topics