🧭 Conceptual Foundation & Pattern Intuition

Fixed-size sliding windows are the rigid-boundary counterpart to dynamic windows. While dynamic windows (LC 209, LC 3, LC 76) grow and shrink adaptively based on constraint satisfaction, fixed-size windows enforce an immutable aperture width $k = |p|$ across the entire sequence.

🧭 Conceptual Foundation & Pattern Intuition

An anagram is any permutation of characters. The foundational insight is that two strings are anagrams if and only if their character frequency distributions are identical:

$\vec{f}_s = \vec{f}_p \iff \text{substring } s[L..R] \text{ is an anagram of } p$

Because character arrangement inside the window is completely irrelevant, we never need to sort substrings or generate permutations. The algorithm only needs to verify whether the current $k$-length window matches $p$'s character histogram.

A naive approach tests every candidate starting index $i \in [0, |s| - |p|]$, taking a slice $s[i..i+k-1]$ and counting or sorting its letters. Recomputing frequencies for $k$ characters takes $O(k)$ work per position. Across all $(|s| - |p| + 1)$ windows, the total runtime degrades quadratically to:

$T_{\text{naive}} = O(|s| \cdot |p|)$

When $|s| = 30,000$ and $|p| = 10,000$, this requires up to $3 \times 10^8$ operations—triggering a guaranteed Time Limit Exceeded (TLE) failure in technical interviews.

📐 Fixed-Width Viewport Mental Model

A fixed window of length $k = |p|$ maintains the strict invariant $R - L + 1 = k$. As the window shifts right by 1, only two characters change state: the exiting character on the left boundary is decremented, and the entering character on the right boundary is incremented.

String s:   | c | b | a | e | b | a | b | a | c | d |
Indices:      0   1   2   3   4   5   6   7   8   9
Target p:    "abc" (len = 3) -> requires {a: 1, b: 1, c: 1}
 
Window 0:   [ c   b   a ]                             -> freq: {a:1, b:1, c:1} == p -> MATCH! (Index 0)
                          slide +1: drop s[0]='c', add s[3]='e'
Window 1:         [ b   a   e ]                       -> freq: {a:1, b:1, e:1} != p -> Miss
                          slide +1: drop s[1]='b', add s[4]='b'
Window 2:             [ a   e   b ]                   -> freq: {a:1, b:1, e:1} != p -> Miss
...
Window 6:                                 [ b   a   c ] -> freq: {a:1, b:1, c:1} == p -> MATCH! (Index 6)
 

🎞️ The Analogy: The Rigid Cardboard Stencil on a Conveyor Belt

Imagine an industrial conveyor belt carrying a continuous stream of letter tiles. Mounted directly above the belt is a stationary cardboard stencil with an open aperture window exactly $k$ tiles wide.

When the conveyor belt rolls forward by one position:

1. The $k - 1$ center tiles stay completely visible inside the aperture. Their counts do not change at all.
2. Exactly one tile passes out of view on the left edge (outgoing = s[i - k]). We subtract it from our tally: window_count[outgoing] -= 1.
3. Exactly one new tile rolls into view on the right edge (incoming = s[i]). We add it to our tally: window_count[incoming] += 1.

Re-counting all $k$ tiles under the stencil on every step is redundant recomputation. By updating only the boundary delta (+1 incoming, -1 outgoing), state maintenance requires strictly $O(1)$ constant operations per slide!

🔑 The Key Idea in the Code

There are two primary paradigms to manage and verify frequency equality:

Paradigm A: The Fixed 26-Element Array ($O(\Sigma)$ Comparison)

Because strings consist of lowercase English letters, we allocate two 26-element arrays ([0] * 26):

p_count, window_count = [0] * 26, [0] * 26
for ch in p:
    p_count[ord(ch) - ord('a')] += 1
for ch in s[:k]:
    window_count[ord(ch) - ord('a')] += 1    # First window: s[0..k-1]
 
result = [0] if window_count == p_count else []
for i in range(k, len(s)):
    window_count[ord(s[i]) - ord('a')] += 1       # Add incoming s[i]
    window_count[ord(s[i - k]) - ord('a')] -= 1   # Remove outgoing s[i - k]
    if window_count == p_count:                   # O(26) = O(1) array equality check
        result.append(i - k + 1)                  # Window s[i - k + 1..i]
 

Because the alphabet size $\Sigma = 26$ is constant, comparing the two 26-element arrays takes exactly 26 machine word comparisons—which is mathematically $O(1)$. Total time is strictly $O(|s| \cdot 26) = O(|s|)$.

Paradigm B: The FAANG $O(1)$ Scalar matches Counter (Zero-Scan Optimization)

Can we evaluate whether the window is valid without even doing 26 comparisons per step? Yes. We maintain an integer register matches (from $0$ to $26$), indicating how many of the 26 characters currently have matching counts in both $s$ and $p$.

• On each slide, only two characters alter their frequencies: the incoming character and the outgoing character.
• Before modifying a character's count, we check if it currently matches p_count. If modifying it breaks a match, we decrement matches -= 1.
• After modifying its count, if it now equals p_count, we increment matches += 1.
• The entire window is an anagram if and only if matches == 26! This evaluates window validity in strictly $O(1)$ operations with zero array scanning, making it optimal even for large Unicode or ASCII alphabets.

⚖️ Brute Force vs. Fixed Sliding Window

💡 The 4-Step Fixed-Window Recipe for Interviews

Whenever an interview problem asks about a contiguous substring/subarray of fixed length $k$:

1. Guard Condition: Immediately return empty/default if $|s| < k$.
2. Seed State: Process the first $k$ elements into the window state accumulator (s[0..k-1]).
3. Roll the Aperture: Iterate $i$ from $k$ to $|s|-1$. At each step:
   • Ingest s[i] into state.
   • Evict s[i - k] from state.
4. Evaluate & Collect: Check state condition in $O(1)$ and record the 0-indexed start position i - k + 1.