Find All Anagrams in a String (LeetCode 438)

The problem

You get a string s and a pattern p. Return the list of every start index in s where a substring of length len(p) is an anagram of p (same letters, same counts, any order). The order of the output doesn’t matter.

Input:  s = "cbaebabacd", p = "abc"
Output: [0, 6]

"cba" starts at index 0 and "bac" starts at index 6. Both are rearrangements of "abc".

How to think about it

Start with brute force. For each start index, take the substring of length m = len(p) and check whether it’s an anagram of p, by sorting or counting. That’s O(n · m) at best.

Anagram means equal counts. Two strings are anagrams exactly when their letter counts match. And every candidate substring has the same fixed length m. So you’re comparing a fixed-size window’s counts against a target.

The key insight: update the counts as the window slides. Neighbouring windows differ by one character in and one character out. Keep a running win count map and adjust just those two letters per step, instead of recounting. Compare win with need after each slide, and record the start index i - m + 1 whenever they’re equal.

Which pattern is this? A fixed-size sliding window with a frequency map. It’s the same as Permutation in String, except you collect all matches rather than returning on the first. The tell is “find all anagrams/permutations of a pattern inside a text”.

Approach

1. If p is longer than s, return [].
2. Build need = Counter(p) and win = counts of the first m characters of s. If equal, record 0.
3. For each i from m to the end: add s[i], decrement s[i - m], and delete it from win if its count drops to 0.
4. If win == need, record i - m + 1, the start of the current window.
5. Return the list.

Solution

from collections import Counter

def find_anagrams(s, p):
    if len(p) > len(s): return []
    need = Counter(p); win = Counter(s[:len(p)]); res = []
    if win == need: res.append(0)                        # first window
    for i in range(len(p), len(s)):
        win[s[i]] += 1; left = s[i-len(p)]; win[left] -= 1   # slide by one
        if win[left] == 0: del win[left]
        if win == need: res.append(i - len(p) + 1)       # window start index
    return res
# find_anagrams("cbaebabacd", "abc") -> [0, 6]

Dry run

On s = "cbaebabacd", p = "abc" (window length 3):

(Windows at i = 4 and i = 6 are aeb and bab, neither a match.) The result is [0, 6].

Complexity

• Time: O(n). Each slide is O(1), and each comparison is over at most 26 keys, so O(26·n).
• Space: O(26) = O(1) for the two maps, plus the output list.

Edge cases and pitfalls

• p longer than s returns [] before slicing.
• Overlapping matches (s = "abab", p = "ab" gives [0, 1, 2]) are all reported; the window moves by one each time.
• Recording i instead of i - len(p) + 1 reports the window’s end, not its start.
• Forgetting the first window misses a match at index 0.
• Leaving zero counts in win can make equal windows compare unequal in many languages; delete them or compare fixed 26-length arrays.

Related problems

• Permutation in String (LeetCode 567): the same window, returning True on the first match.
• Group Anagrams (LeetCode 49): grouping whole words by their letter counts.
• Maximum Average Subarray I (LeetCode 643): the simplest fixed-size window, with a sum instead of counts.