Find All Anagrams in a String

Sliding WindowHash Map

30 min

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.

Example

Example 1:

Input: s = "cbaebabacd", p = "abc"

s: "cbaebabacd", p: "abc"

Output: [0, 6]

Output: [0,6]

The substring with start index 0 is "cba", which is an anagram of "abc". The substring with start index 6 is "bac", which is an anagram of "abc".

Solution

This problem can be solved using a sliding window and two hash maps. One map stores the frequency of characters in `p`, and the other stores the frequency of characters in the current window of `s`. We slide the window and compare the maps.

Algorithm Steps

Create a frequency map for the characters in `p`.
Initialize a second frequency map for the window in `s`.
Slide a window of size `p.length()` over `s`.
For each window, update the window's frequency map.
If the two frequency maps are identical, add the starting index of the window to the result list.

Find All Anagrams in a String

Sliding Window with Hash Maps

Progress1 / 1

Ready to start the visualization

p Map

s Window Map

Result

Find All Anagrams in a String Solution


from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        if len(p) > len(s):
            return []
        
        p_count, s_count = Counter(p), Counter(s[:len(p)])
        res = [0] if s_count == p_count else []
        
        l = 0
        for r in range(len(p), len(s)):
            s_count[s[r]] = 1 + s_count.get(s[r], 0)
            s_count[s[l]] -= 1
            
            if s_count[s[l]] == 0:
                del s_count[s[l]]
            l += 1
            if s_count == p_count:
                res.append(l)
        return res