Find All Anagrams in a String — Fixed Sliding Window With Frequency Matching

Problem Statement#

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An anagram is a rearrangement of all the characters of a string.

Constraints:

• 1 <= s.length, p.length <= 3 * 10^4
• s and p consist of lowercase English letters.

Example 1:
Input:  s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation:
  s[0..2] = "cba" → anagram of "abc" ✓
  s[6..8] = "bac" → anagram of "abc" ✓

Example 2:
Input:  s = "abab", p = "ab"
Output: [0, 1, 2]
Explanation:
  s[0..1] = "ab" ✓, s[1..2] = "ba" ✓, s[2..3] = "ab" ✓

Example 3:
Input:  s = "aa", p = "bb"
Output: []

Why This Problem Matters#

Find All Anagrams in a String is one of the most important sliding window problems at Google and Amazon because it requires you to maintain a frequency match state as you slide a fixed-size window across a string. The naive approach — recompute the frequency count of the entire window at each position — costs O(n * k) where k is the pattern length. The optimized approach updates the window incrementally and tracks a "match count" variable, reducing each step to O(1) and the total to O(n).

This problem appears as a direct filter in Google coding interviews because it combines two patterns that must both be mastered: the fixed sliding window (maintaining a window of exactly len(p) characters) and the frequency match state (tracking how many character frequencies in the window match the pattern). Candidates who know only one pattern but not both will produce a correct but slow solution.

The match-counter optimization is worth understanding deeply. Instead of comparing two 26-element frequency arrays at every step (O(26) = O(1) constant but with a large constant), you track a single integer matches that represents how many character types currently have matching frequencies. When matches == len(need) (number of distinct character types in p), the window is an anagram. Updating matches as you add or remove characters from the window requires careful case analysis but reduces the constant factor significantly.

This problem is also a direct generalization of Permutation in String (LC 567) — the only difference is that LC 567 returns a boolean (any anagram exists) while this problem returns all starting positions.

The Core Insight#

A window of size len(p) starting at index i is an anagram of p if the character frequency distributions are identical.

Naive approach: Maintain a frequency counter for the current window. At each position, compare it to p's frequency counter. O(n * 26) = O(n) with a constant factor of 26.

Optimized approach with match counter: Track the number of character types where the window's frequency exactly matches p's frequency. Initialize this count from the first window. As you slide the window:

• Add the incoming character c_in = s[i]:
  • If c_in is in p's need-map, check if its window count was just below the required count (matches increases) or just exceeded it (matches decreases).
• Remove the outgoing character c_out = s[i - len(p)]:
  • Similar logic: if removing c_out causes it to fall back to exactly the required count, matches increases. If it falls below, matches decreases.

When matches == number of distinct character types in p, the window is an anagram.

Visual Dry Run#

Input: s = "cbaebabacd", p = "abc"

need = {a:1, b:1, c:1}, len(need) = 3

Initialize window over s[0..2] = "cba": window = {c:1, b:1, a:1}, matches = 3 → add index 0 to result.

Slide to s[1..3] = "bae":

• Remove s[0] = 'c': window[c] drops from 1 to 0, need is 1 → matches drops from 3 to 2.
• Add s[3] = 'e': e not in need, no change. matches = 2.
• Window {b:1, a:1, e:1} ≠ need. No match.

Slide to s[2..4] = "aeb":

• Remove s[1] = 'b': window[b] drops below need → matches drops to 1.
• Add s[4] = 'e': not in need. matches = 1. No match.

... (slides through indices 3–5 with no matches) ...

At s[6..8] = "bac": window = {b:1, a:1, c:1}, matches = 3 → add index 6 to result.

Result: [0, 6]

Solution (Optimal)#

from collections import Counter
 
def findAnagrams(s: str, p: str) -> list[int]:
    k = len(p)
    if len(s) < k:
        return []
 
    need = Counter(p)              # Frequency map for p
    window = Counter(s[:k])        # Frequency map for the first window
    result = []
 
    # Count initial matches (character types with matching frequencies)
    matches = sum(1 for ch in need if window[ch] == need[ch])
    if matches == len(need):
        result.append(0)
 
    for i in range(k, len(s)):
        c_in = s[i]
        c_out = s[i - k]
 
        # --- Add incoming character ---
        window[c_in] += 1
        if c_in in need:
            if window[c_in] == need[c_in]:
                matches += 1        # Went from under to exact
            elif window[c_in] == need[c_in] + 1:
                matches -= 1        # Went from exact to over
 
        # --- Remove outgoing character ---
        window[c_out] -= 1
        if c_out in need:
            if window[c_out] == need[c_out]:
                matches += 1        # Went from over to exact
            elif window[c_out] == need[c_out] - 1:
                matches -= 1        # Went from exact to under
        if window[c_out] == 0:
            del window[c_out]
 
        if matches == len(need):
            result.append(i - k + 1)
 
    return result
 
 
# Simple approach: compare 26-element arrays — O(26n) = O(n)
def findAnagrams_simple(s: str, p: str) -> list[int]:
    k = len(p)
    if len(s) < k:
        return []
 
    need = [0] * 26
    for ch in p:
        need[ord(ch) - 97] += 1
 
    window = [0] * 26
    for ch in s[:k]:
        window[ord(ch) - 97] += 1
 
    result = []
    if window == need:
        result.append(0)
 
    for i in range(k, len(s)):
        window[ord(s[i]) - 97] += 1
        window[ord(s[i - k]) - 97] -= 1
        if window == need:
            result.append(i - k + 1)
 
    return result

var findAnagrams = function(s, p) {
    const k = p.length;
    if (s.length < k) return [];
 
    const need = new Array(26).fill(0);
    const window = new Array(26).fill(0);
 
    for (const ch of p) need[ch.charCodeAt(0) - 97]++;
    for (let i = 0; i < k; i++) window[s.charCodeAt(i) - 97]++;
 
    const result = [];
    const arraysEqual = () => need.every((v, i) => v === window[i]);
 
    if (arraysEqual()) result.push(0);
 
    for (let i = k; i < s.length; i++) {
        window[s.charCodeAt(i) - 97]++;
        window[s.charCodeAt(i - k) - 97]--;
        if (arraysEqual()) result.push(i - k + 1);
    }
 
    return result;
};

Complexity Analysis

Both the 26-array and match-counter approaches are O(n) with O(1) space. For this problem with the given constraints, both are fast enough. The match-counter approach is worth knowing for the conceptual depth it demonstrates.

Common Mistakes#

• Comparing window == need on dictionaries after deletions. Python Counter comparison works, but if you delete keys where count is 0, the comparison may fail because need still has those keys. Either keep zero-count keys in both counters, or use the array approach.
• Off-by-one in the sliding window. When i = k, the window is s[1..k]: add s[k] (index k) and remove s[0] (index i - k = 0). Verify the formula s[i - k] is the outgoing character.
• Not initializing the first window before the loop. The loop starts at index k, so the first window s[0..k-1] must be initialized separately.
• Forgetting to check the first window for a match. The loop starts at i = k and adds the result for the window ending at i. But the first window (starting at index 0) must be checked before the loop begins.
• Using the match-counter logic incorrectly. The edge cases — "went from under to exact" vs. "went from exact to over" — require careful case analysis. When in doubt, use the simpler 26-array comparison approach for correctness.

Follow-up Questions#

How does this differ from Permutation in String (LC 567)? LC 567 asks whether any anagram of p exists as a substring of s (return boolean). This problem asks for all starting indices of such anagrams. The algorithm is identical; this problem collects all matches instead of returning on the first one.

What if the pattern p is longer than s? Return an empty list immediately — no window of size len(p) can fit in s.

How would you handle a case-insensitive search? Normalize both s and p to lowercase before building frequency arrays. Everything else stays the same.

What if you need to find anagrams with at most one character difference (fuzzy matching)? Track how many character types are mismatched. When mismatches <= 1, the window qualifies. This is a more complex variant that requires tracking over- and under-counts separately.

What is the minimum window size that contains all characters of p (not necessarily an anagram)? This is the Minimum Window Substring problem (LC 76). It uses a variable-length sliding window instead of a fixed-length one.

Key Takeaways#

• LC 438 Find All Anagrams combines fixed-window sliding with frequency-array equality.
• Maintain need (frequency of p) and window (frequency of the current s slice of length len(p)).
• On each shift: increment the entering character's count, decrement the leaving character's count, then compare arrays.
• Comparing two 26-element arrays is O(26) = O(1), so the full algorithm is O(n).
• Track a matches integer (number of indices where window[i] == need[i]) for true O(1) per shift instead of full-array equality.
• Time O(n + m), space O(1) for fixed alphabet — optimal.
• Pattern generalizes to LC 567 (single permutation match), LC 76 (variable-length window), and DNA motif scanning in bioinformatics.

Related Problems#

• LC 438 — Find All Anagrams in a String: This problem.
• LC 567 — Permutation in String: Return boolean instead of all indices — simpler version.
• LC 76 — Minimum Window Substring: Variable-length window that must contain all characters of p.
• LC 3 — Longest Substring Without Repeating Characters: Variable-length window with a uniqueness constraint.
• LC 242 — Valid Anagram: Check if two fixed strings are anagrams — no sliding window needed.
• LC 49 — Group Anagrams: Group a list of strings by anagram class.