Pattern 2: Sliding Window with frequency

The sliding window you learned in Array comes back here — except the window's state stops being a number and becomes a count map. With that, it solves the largest family of string problems on LeetCode.

Tried it? Generating all substrings and checking for repeats in each is O(n²) or O(n³). The annoyance: when you move the start, you restart the check from scratch. The theory below brings the sliding window back — now with a richer state.

The theory: the window gets a richer state

Recall the variable-window template (Array section): right expands, and a while shrinks left while the window violates the condition. The skeleton is identical here — what changes is what the window carries and what counts as a violation.

left = 0
contagem = {}            # ← the state is now a frequency map
for right from 0 to n-1:
    contagem[s[right]] += 1            # char enters from the right
    while the window is INVALID:
        contagem[s[left]] -= 1         # char leaves from the left
        left += 1
    record the best (window [left..right] is valid)

The definition of "invalid" changes per problem: does it have a repeated char?, do we need to swap more than k chars?, is some letter of the target still uncovered?. All of this is read from the count map.

And the reason it's O(n) is the same as in the Array section: each character enters the window once (right) and leaves at most once (left) — at most 2n moves, each O(1). The inner while doesn't make this O(n²).

The signs in the prompt

• "longest/shortest substring (contiguous!) that satisfies ..." .
• A condition over the characters inside the window ("no repeats", "at most k distinct", "contains all letters of t").
• The crucial difference from the previous lesson: here order and contiguity matter (it's a substring), not just the composition.

Example 1 — Longest Substring Without Repeating Characters

"Longest substring with no repeated characters." The validity condition: no letter appears twice in the window.

• Brute force: test all substrings and check for repeats — O(n²) or O(n³).
• The waste: when we move the start, we restart the check from scratch.
• The pattern: always expand right; if the new char is already in the window, shrink left until you remove the repeat. The state is the set of chars in the window.

Watch the window [left..right] grow and shrink — notice that left only advances when right brings in a repeated character:

The window always contains unique characters, and the answer is the largest size right - left + 1 seen. O(n) time; O(min(n, alphabet)) space for the map.

Example 2 — Longest Repeating Character Replacement

"Longest substring that becomes a block of a single letter by swapping at most k characters." The validity condition gets subtler:

window size − (count of its most frequent character) ≤ k

In other words: the characters that are not the majority are the ones you'd have to swap; if there are ≤ k of them, the window is valid. The count map is what lets you know, in O(1), which is the window's most frequent character.

Why is it O(n)?

A single pass of right (n times); left never goes backward. The map operations and the max are O(1). The same irreversible-progress argument from the Array section: each char enters and leaves at most once. O(n), O(1) space (fixed alphabet).

Example 3 — Minimum Window Substring (the section's boss)

"Smallest substring of s that contains all the letters of t (with multiplicity)." It's the sliding window with frequency at its peak:

1. Build the target frequency (of t).
2. Expand right, counting the window's characters.
3. When the window covers the whole target, try to shrink left as much as possible without losing coverage — recording the smallest valid window.

Here the window wants to be minimal (not maximal): the shrinking while runs while the window stays valid, unlike the previous examples. It's the same structure, with the direction of optimization reversed — a good sign that you understood the pattern rather than memorized a case.

Sliding window or fixed counting? (lesson 2 vs lesson 3)

• Does the composition of the whole string matter (anagram, group)? → fixed counting (lesson 2).
• Is the condition about a contiguous substring that grows/shrinks? → sliding window (this lesson).

Summary

• A string sliding window = the Array template + state = frequency map.
• The window's "validity" is read from the map: no repeats / ≤ k swaps / covers the target.
• O(n) always, by the same argument: each char enters and leaves at most once.
• A maximal window shrinks on violation; a minimal window shrinks while it holds.

Next lesson: back to two pointers — this time for palindromes.