Find All Anagrams in a String – Brute-Force to Optimal Solution

If you're trying to find all anagrams of a pattern p in a string s, you’re working with one of the most classic sliding window problems in string algorithms.

As engineers who work with high-performance text processing and data streaming systems, we’ve solved this problem hundreds of times, and here’s how you can go from brute-force to blazing fast solutions step-by-step.

What’s the Problem?

You're given:

• A string s (the haystack)

• A pattern p (the needle)

You want to return all the starting indices in s where an anagram of p begins.

Example:

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation: Anagrams "cba" and "bac" start at indices 0 and 6.

Step 1 – Brute Force (Too Slow, Don't Use in Production)

Let’s start with the most basic idea:

1. Slide over every possible substring in s.

2. Check if it’s an anagram of p.

def is_anagram(res, dp):
    for i in dp:
        if res.count(i) != dp[i]:
            return False
    return len(res) == sum(dp.values())

def all_anagrams(s: str, p: str):
    dp = {}
    for i in p:
        dp[i] = dp.get(i, 0) + 1

    fin = []
    for i in range(len(s)):
        test = s[i:i + len(p)]
        if len(test) != len(p):
            continue
        if is_anagram(test, dp):
            fin.append(i)
    return fin

print("Expected:[0,1,2], Actual:", all_anagrams("abab", "ab"))
print("Expected:[0,6], Actual:", all_anagrams("cbaebabacd", "abc"))
print("Expected:[99999], Actual:", all_anagrams("a"*10**5 + "b", "ab"))
print("Expected:many results, Actual:", all_anagrams("abcde"*200000, "edcba"))
print("Expected:many results, Actual:", all_anagrams("abcd"*250000, "dcba"))

Why It’s Bad:

• Time Complexity: O(N * M), where N is the length of s and M is the length of p.

• Space Complexity: O(M) for temporary slices and frequency maps.

• res.count() is called repeatedly → super slow for big inputs.

Step 2 – Smarter Brute Force (Still Not Enough)

What’s the improvement?

In the brute-force solution from Step 1, we:

• Extract every possible substring of any length (which was too much).

• Count each character in the substring from scratch.

In Step 2, we:

• Only look at substrings of length equal to len(p) (because anagrams must be same length).

• Precompute the frequency of p once.

• Avoid checking substrings of wrong length.

We still check every substring of length len(p), but now we only compare frequencies.

Key Insight:

Every anagram of p must:

• Have the exact same length

• Have the same count of each character

So, we can:

• Build a frequency map for p

• Slide through s using substrings of same length

• Build a frequency map for each substring

• Compare the two maps

Code: Smarter Brute Force

from typing import List
from collections import Counter

def smarter_brute_force(s: str, p: str) -> List[int]:
    """
    Finds all anagrams of p in s using substring slicing + frequency comparison.
    This is better than naive brute-force but still not optimal.
    """
    if len(p) > len(s):
        return []

    result = []
    p_len = len(p)
    p_count = Counter(p)

    for i in range(len(s) - p_len + 1):
        window = s[i:i + p_len]
        window_count = Counter(window)
        if window_count == p_count:
            result.append(i)

    return result

Time and Space Complexity:

• Time:

  • Creating p_count: O(M) where M = len(p)

  • For each of N−M+1 windows:

    • Create window string: O(M)

    • Create Counter for window: O(M)

    • Compare two Counters: O(M)

  Total: O((N−M+1) × M) ⇒ O(N × M)

• Space: O(M) for p_count, O(M)  per window

Step 3 – The Optimal Solution Using Sliding Window + Hash Map

Let’s optimize this like a pro.

Use the Sliding Window pattern and two hash maps (or arrays if limited to lowercase letters) to track the frequency of characters in:

• p

• current window in s

We slide a window of length len(p) through s, updating the counts on the fly.

from typing import List
from collections import Counter

def find_anagrams(s: str, p: str) -> List[int]:
    """
    Returns start indices of all anagrams of 'p' in string 's'.
    """
    if len(p) > len(s):
        return []

    p_count = Counter(p)              # Frequency map of pattern
    s_count = Counter(s[:len(p)])     # Frequency map of first window

    result = []
    if s_count == p_count:
        result.append(0)

    for i in range(len(p), len(s)):
        s_count[s[i]] += 1            # include new character to window
        s_count[s[i - len(p)]] -= 1   # remove old character from window

        if s_count[s[i - len(p)]] == 0:
            del s_count[s[i - len(p)]]

        if s_count == p_count:
            result.append(i - len(p) + 1)

    return result

Let’s Break It Down Like You’re Two

• You count how many letters are in your toy box (that’s the pattern p).

• You move a window across your bookshelf (string s) the same size as your toy box.

• Every time your shelf window has the same toys (letters) as your toy box, you shout “Match!”

• You write down the shelf number.

What Makes This Fast?

• Pattern Used: Sliding Window + Hash Map comparison

• Data Structures: collections.Counter (or a fixed-size array if s only has lowercase letters)

• Time Complexity: O(N), where N is the length of s

• Space Complexity: O(1) if alphabet size is fixed (e.g. 26 lowercase letters), otherwise O(K) where K = size of character set

How to Recognize This Pattern

• The problem talks about substrings or windows of a fixed size.

• You’re comparing frequencies or counts of characters or elements.

• The pattern is looking for repeated matching substrings or anagrams.

If you’re counting things in a sliding range, you likely need a sliding window.

How Could I Derive This On My Own?

1. Think about the brute-force way first: slice every possible substring and check it.

2. Ask: Is there any unnecessary repetition?

3. Look for things you can compute once and update slightly on each move.

4. When you see substring comparisons of same length  think sliding window.

5. If you see you’re comparing character makeup  think frequency maps.

What You Should Do Next

You’ve just learned how to take a brute-force algorithm and make it super efficient using sliding windows and hash maps.

Here’s what to try next:

• Solve variations: Find all permutations in string, Longest substring with same characters, Minimum window substring

• Try replacing Counter with arrays for optimization

• Try writing your own pattern recognizer: every time a problem asks for repeated substrings or fixed-length patterns, pause and ask yourself: Sliding Window?

Want More Pattern-Based Solutions?

Start building your own “pattern toolbox” — subscribe to get free deep-dives on 50+ algorithm patterns with code, visuals, and real-world analogies.