Find All Anagrams in a String

Intuition

An anagram is fully described by how many of each letter it contains, so two strings are anagrams exactly when their letter-count vectors are equal. Because the window is a fixed length, each step adds one letter on the right and removes one on the left, updating the tally in constant time. Comparing the window tally against p's tally at each valid position pinpoints all anagram starts in a single pass.

Algorithm walkthrough

1. 1Build a 26-length count of p and a matching count for the first window of s.
2. 2Slide the window one character at a time: add the entering character and, once the window is full length, subtract the leaving character.
3. 3Whenever the window has reached the length of p, compare its count vector with p's count vector.
4. 4If the two vectors are identical, append the window's starting index to the results.
5. 5After the final position is checked, return the collected indices.

Implementation

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        if len(p) > len(s):
            return result
        need = [0] * 26
        window = [0] * 26
        base = ord('a')
        for c in p:
            need[ord(c) - base] += 1
        for i, ch in enumerate(s):
            window[ord(ch) - base] += 1
            if i >= len(p):
                window[ord(s[i - len(p)]) - base] -= 1
            if i >= len(p) - 1 and window == need:
                result.append(i - len(p) + 1)
        return result