deepSWE.io

Find All Anagrams in a String

Hashing

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"

Output: [0, 6]

Solution (Sliding Window & Hash Map)

This problem can be solved using a sliding window approach with two hash maps. One map stores the character frequencies of the pattern `p`, and the other stores the frequencies of the current window in `s`.

Algorithm Steps

Create a frequency map for the pattern `p`.
Initialize a sliding window and a frequency map for the window.
Iterate through the string `s` with the sliding window.
As the window slides, update the window's frequency map.
At each step, compare the window's frequency map with the pattern's frequency map.
If they are equal, add the starting index of the window to the result list.

String s:

String p:

String s

Window Character Counts

Created frequency map for p: {"a":1,"b":1,"c":1}.

Find All Anagrams in a String Solution


from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        ns, np = len(s), len(p)
        if ns < np:
            return []

        p_count = Counter(p)
        s_count = Counter()
        
        output = []
        # sliding window on the string s
        for i in range(ns):
            # add one more letter 
            # on the right side of the window
            s_count[s[i]] += 1
            # remove one letter 
            # from the left side of the window
            if i >= np:
                if s_count[s[i - np]] == 1:
                    del s_count[s[i - np]]
                else:
                    s_count[s[i - np]] -= 1
            # compare array in the sliding window
            # with the reference array
            if p_count == s_count:
                output.append(i - np + 1)
        
        return output