Find All Anagrams in a String With One Sliding Histogram

If you interview at Amazon, Meta, Adobe, expect some version of "Find All Anagrams in a String". It is rated Medium, and it falls squarely into the Sliding Window pattern — pattern-first preparation beats grinding random problems every time. Part 6 of 11 in the Sliding Window arc.

The Problem

Given strings s and p, return all start indices of p's anagrams in s, in order. Same engine as Permutation in String, but you emit every hit instead of returning at the first — which changes nothing structurally and tests whether you actually own the template.

Input:  s = "cbaebabacd", p = "abc"
Output: [0, 6]
Windows "cba" and "bac" are anagrams of "abc".

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Fixed window of length len(p), frequency-histogram aggregate, collect all valid positions. When a problem is a previously seen one with the return type changed, say so explicitly — interviewers reward recognizing isomorphic problems.

The Approach

Maintain the window histogram and a deficit count of how many letters still differ from p's histogram. Slide one character in, one out, adjusting deficit on the at-most-two letters whose counts change. Zero deficit at any position appends right - n + 1 to the results.

Using deficit-of-letters rather than matches-of-26 is an equivalent bookkeeping choice — pick one, name the other, move on.

Python Solution

def find_anagrams(s: str, p: str) -> list[int]:
    """All start indices where a window of s is an anagram of p."""
    n, m = len(p), len(s)
    if n > m:
        return []

    from collections import Counter
    need = Counter(p)
    window = Counter(s[:n])
    result = []
    if window == need:
        result.append(0)

    for right in range(n, m):
        window[s[right]] += 1
        out = s[right - n]
        window[out] -= 1
        if window[out] == 0:
            del window[out]           # keep Counter equality honest
        if window == need:
            result.append(right - n + 1)
    return result

Complexity

• Time: O(n + m·k) — k bounded by alphabet size for the Counter comparison; O(n + m) with a match counter
• Space: O(1) — histograms bounded by the alphabet

Interview Tips and Follow-Ups

• The del window[out] line is the classic bug: a zero-count key makes Counter equality fail silently. Know why it is there.
• State the upgrade path: replace Counter equality with the 26-match counter from Permutation in String for strict O(n + m).
• Emitting indices vs booleans changes memory of the output only — say it to show you separate algorithm from interface.

If this clicked, continue the Sliding Window arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.