Find All Anagrams in a String | Leetcode 438

Welcome to our deep dive on Find All Anagrams in a String (Leetcode 438). This string problem elegantly applies a Sliding Window strategy over an array-based HashMap.

Problem Statement

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example: s = "cbaebabacd", p = "abc" => Output: [0,6] (Explanation: The substring "cba" starting at index 0 and "bac" starting at index 6 are anagrams of "abc".)

Approach: Fixed-Size Sliding Window O(N)

Since an anagram is precisely defined by matching character frequencies, we can track the "state" of our search using an array of size 26 (for a-z). If the frequency array of a substring exactly matches the frequency array of p, then that substring is guaranteed to be an anagram!

Because every valid anagram has exactly the same length as p, this makes our Sliding Window a Fixed-Size window!

1. Create a p_count array of size 26 to store the target frequencies.
2. Initialize an s_count tracking array of size 26.
3. Slide a window of length len(p) across s.
4. At each step, we expand our window on the right by incrementing the new character's frequency in s_count.
5. Simultaneously, we contract our window on the left by decrementing the old character's frequency.
6. Compare p_count to s_count. If they are identical, we record the start index of the window!

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s): 
            return []
            
        p_count = [0] * 26
        s_count = [0] * 26
        res = []
        
        # Initialize target Map
        for char in p:
            p_count[ord(char) - ord('a')] += 1
            
        # Initialize first window
        for i in range(len(p)):
            s_count[ord(s[i]) - ord('a')] += 1
            
        # Check first window
        if s_count == p_count:
            res.append(0)
            
        # Slide Window
        left = 0
        for right in range(len(p), len(s)):
            s_count[ord(s[right]) - ord('a')] += 1
            s_count[ord(s[left]) - ord('a')] -= 1
            
            left += 1
            if s_count == p_count:
                res.append(left)
                
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (438)