Find All Anagrams in a String: Sliding Window Frequency Match

LeetCode's Find All Anagrams in a String (LeetCode 438) asks you to find every position in a string s where a substring of the same length as p is an anagram of p. You return a list of starting indices.

For example, given s = "cbaebabacd" and p = "abc", the answer is [0, 6] because "cba" starting at index 0 and "bac" starting at index 6 are both anagrams of "abc".

If you have worked through Minimum Window Substring or Longest Substring Without Repeating Characters, you already know the sliding window skeleton. This problem is actually simpler because the window size is fixed: it is always len(p). That constraint makes the slide predictable and the logic cleaner.

Why this problem matters

This is one of the best problems for learning how to combine two fundamental patterns: the sliding window and the frequency map. You will see both of these building blocks again and again in string problems, and this particular combination shows up in Minimum Window Substring, Permutation in String, and Longest Substring with At Most K Distinct Characters.

The fixed-size window variant here is the gentlest introduction to frequency-based sliding window. Once you internalize this approach, the variable-size versions feel like natural extensions.

The key insight

A naive approach would sort every window of length len(p) and compare it to the sorted version of p. That works, but sorting each window costs O(k log k) where k is the length of p, giving you O(n * k log k) overall.

The insight is that two strings are anagrams if and only if they have the same character frequencies. Instead of sorting, maintain a frequency count for the current window and compare it to the frequency count for p. When you slide the window one position to the right, you remove one character on the left and add one character on the right, doing O(1) work per slide.

The second optimization is the "match count" trick. Instead of comparing the full frequency maps on every slide (which costs O(26) per step), track how many characters currently have matching counts between the window and p. When the match count equals the number of unique characters in p, you have found an anagram. Updating the match count on each slide is O(1).

The solution

def find_anagrams(s, p):
    if len(p) > len(s):
        return []

    from collections import Counter

    p_count = Counter(p)
    window_count = Counter()
    result = []

    required = len(p_count)  # unique chars in p
    formed = 0               # chars with matching counts

    for i in range(len(s)):
        # Add the new character on the right
        ch = s[i]
        window_count[ch] += 1

        # Check if this character's count now matches p
        if ch in p_count and window_count[ch] == p_count[ch]:
            formed += 1

        # Remove the character sliding out on the left
        if i >= len(p):
            left_ch = s[i - len(p)]
            if left_ch in p_count and window_count[left_ch] == p_count[left_ch]:
                formed -= 1
            window_count[left_ch] -= 1

        # If all character counts match, record this index
        if formed == required:
            result.append(i - len(p) + 1)

    return result

Let's walk through the important parts:

1. p_count is a Counter that tells you how many of each character you need. For p = "abc", that is {a: 1, b: 1, c: 1}.
2. required is the number of unique characters in p. We need formed to reach this number.
3. On each step, we add s[i] to the window. If i >= len(p), we also remove the character that just slid out the left side.
4. The formed counter goes up when a character's window count reaches its required count, and goes down when a character's window count drops below its required count.
5. When formed == required, every character in the window matches the pattern frequencies, so we record the starting index.

Visual walkthrough

Notice how each step does exactly two things: remove one character from the left side of the window and add one character on the right. The frequency map updates incrementally, never rebuilt from scratch. The match count tells you instantly whether the window is a valid anagram.

Complexity analysis

Time: O(n) where n is the length of s. Each character is added to the window once and removed once. Each addition and removal does O(1) work to update the frequency count and match counter.

Space: O(1). The frequency maps hold at most 26 entries (lowercase English letters). This is constant regardless of input size.

The O(26n) approach is technically O(n) too, but the match count optimization removes that constant factor of 26 per step, which matters in practice on large inputs.

Edge cases

Before submitting, verify your solution handles:

• p longer than s: return []. No window of length len(p) can fit.
• p and s are identical: return [0]. The entire string is one anagram.
• Single character: s = "a", p = "a". Return [0].
• No anagrams exist: s = "abcdef", p = "zz". Return [].
• Overlapping anagrams: s = "aaa", p = "aa". Return [0, 1]. Two overlapping windows both match.
• All characters the same: s = "aaaa", p = "aa". Return [0, 1, 2]. Every window of length 2 is an anagram.

The building blocks

This problem decomposes into two reusable pieces that CodeBricks drills independently:

1. Fixed-size sliding window

The mechanics of sliding a window of constant width across a string. On each step you add one character on the right and remove one on the left. Both pointers advance together, so there is no shrink-while-valid or expand-while-invalid logic. This is the simplest variant of sliding window and the one you should learn first.

for i in range(len(s)):
    # add s[i] to window
    if i >= window_size:
        # remove s[i - window_size] from window
    # check window

This same fixed-size pattern appears in Maximum Sum Subarray of Size K and Sliding Window Maximum.

2. Frequency map with match counting

The technique of maintaining character counts for the window and tracking how many characters have matching frequencies. Instead of comparing entire maps, you update a single counter whenever a character's count crosses the threshold. This is O(1) per update and tells you immediately whether the window satisfies the condition.

# When adding a character
if ch in target and window[ch] == target[ch]:
    formed += 1

# When removing a character
if ch in target and window[ch] == target[ch]:
    formed -= 1
window[ch] -= 1

This same building block powers Minimum Window Substring and Permutation in String. The only difference is the window size: fixed here, variable there.

From understanding to recall

Reading through this solution is the easy part. Reproducing it from memory under time pressure is where most people struggle. The formed counter trick, the order of operations when removing a character (check before decrementing), and the fixed-window index math are all details that fade without practice. Spaced repetition locks them in by having you write the code at increasing intervals until the pattern is automatic.

Related posts

• Longest Substring Without Repeating Characters - The growing-window variant of sliding window, using a set instead of frequency counting
• Minimum Window Substring - The variable-size version of frequency-based sliding window, adding the shrink-while-valid phase
• Valid Anagram - The core frequency comparison technique used inside each window check here