Find All Anagrams in a String Solution

Problem

Given a string s and a pattern p, find every starting index in s where the substring of length len(p) is an anagram of p. Two strings are anagrams if they contain exactly the same characters with the same frequencies.

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation: "cba" at index 0 and "bac" at index 6 are both anagrams of "abc"

Counter-example: "abe" is NOT an anagram of "abc" because 'e' appears in place of 'c', even though both have length 3.

Intuition

The problem reduces to checking whether each length-len(p) window in s has exactly the same character frequencies as p. The key insight is that sliding the window by one position only changes two characters — one enters from the right and one exits from the left. Instead of recomputing the full frequency comparison at each step, we can maintain a count of how many of the 26 letters currently have a matching frequency. When that count reaches 26, the window is an anagram.

Approach 1 — Brute Force

For each starting position, extract the substring and compare its sorted characters to the sorted pattern.

Sort the characters of p once and store as the reference.
For each starting index from 0 to len(s) - len(p): a. Extract the window of size len(p) and sort it. b. If it matches the sorted p, record the start index.
Return all recorded indices.

1def findAnagrams(self, s: str, p: str) -> List[int]:
2    result = []
3    p_sorted = sorted(p)
4    window_size = len(p)
5
6    for start in range(len(s) - window_size + 1):
7        # Sort the current window and compare to sorted p
8        if sorted(s[start:start + window_size]) == p_sorted:
9            result.append(start)
10
11    return result

Time: O(n · m log m) — sorting each window of size m costs O(m log m), repeated for each of the n starting positions.
Space: O(m) — temporary storage for each window copy.

Approach 2 — Sliding Window with Match Counter

Maintain a fixed-size window over s using frequency arrays, and track how many of the 26 letters currently have matching counts. Each slide updates at most two letters and adjusts matches by at most two, giving true O(n) performance.

Build frequency array p_count from p.
Fill window_count with the first len(p) characters of s.
Initialize matches to the number of letters where both arrays agree. If matches == 26, record index 0.
For each subsequent position right: a. Slide in s[right]: if its count was matching, decrement matches; increment its count; if it now matches, increment matches. b. Slide out s[right - len(p)]: same two-check update after decrementing.
If matches == 26 after both updates, record right - len(p) + 1.

1def findAnagrams(self, s: str, p: str) -> List[int]:
2    if len(p) > len(s):
3        return []
4
5    p_count = [0] * 26
6    window_count = [0] * 26
7
8    for char in p:
9        p_count[ord(char) - ord('a')] += 1
10
11    for char in s[:len(p)]:
12        window_count[ord(char) - ord('a')] += 1
13
14    # Count letters whose frequencies match between window and p
15    matches = sum(1 for i in range(26) if window_count[i] == p_count[i])
16    result = [0] if matches == 26 else []
17
18    for right in range(len(p), len(s)):
19        char_in = ord(s[right]) - ord('a')
20        if window_count[char_in] == p_count[char_in]:
21            matches -= 1  # about to break this letter's match
22        window_count[char_in] += 1
23        if window_count[char_in] == p_count[char_in]:
24            matches += 1  # frequency now matches again
25
26        char_out = ord(s[right - len(p)]) - ord('a')
27        if window_count[char_out] == p_count[char_out]:
28            matches -= 1  # about to break this letter's match
29        window_count[char_out] -= 1
30        if window_count[char_out] == p_count[char_out]:
31            matches += 1  # frequency now matches again
32
33        if matches == 26:
34            result.append(right - len(p) + 1)
35
36    return result

Time: O(n) — each character is added and removed from the window exactly once; the per-step work is constant (at most 4 comparisons).
Space: O(1) — two fixed-size arrays of 26 integers regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force (sort each window)	O(n · m log m)	O(m)	Quick correctness check; impractical when n or m is large
Sliding Window (match counter)	O(n)	O(1)	Always — the expected interview solution for any input size

Common Mistakes

Off-by-one when recording the start index: the window ending at right began at right - len(p) + 1, not right or right - len(p).
Skipping the first window: only entering the sliding loop from index len(p) without checking the initial window means index 0 is never tested — check matches once before the loop starts.
Using a HashMap instead of a fixed array: a dict works but adds hashing overhead; since input is restricted to lowercase letters, a 26-element array is both faster and simpler to reason about.
Sliding out before sliding in: the order within each iteration matters — process the incoming character first, then the outgoing one. Reversing the order produces the same result but makes the start-index arithmetic harder to verify at a glance.
Missing the len(p) > len(s) guard: without it, initializing the first window by slicing s[:len(p)] silently returns fewer than len(p) characters in Python, or crashes in Java/C++.

Find All Anagrams in a String — Solution