Find All Anagrams in a String

Patrick Leaton
Published: June 24, 2021, 8:27 p.m.
Problem Description

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 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
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".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

 

Constraints:

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.

 

The description was taken from https://leetcode.com/problems/find-all-anagrams-in-a-string/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
       
        p_chars, s_chars = {}, {}
        left, right = 0, 0
        output = []
       
        for char in p:
            if char not in p_chars:
                p_chars[char] = 1
            else:
                p_chars[char] += 1
       
        while right < len(p)-1:
            if s[right] not in s_chars:
                s_chars[s[right]] = 1
            else:
                s_chars[s[right]] += 1
            right += 1
       
        while right < len(s):
            if s[right] not in s_chars:
                s_chars[s[right]] = 1
            else:
                s_chars[s[right]] += 1
           
            if p_chars == s_chars:
                output.append(left)
           
            s_chars[s[left]] -= 1
            if s_chars[s[left]] == 0:
                del s_chars[s[left]]
               
            left += 1
            right += 1
               
        return output

Problem Explanation

This problem is very similar to Permutation in String.

Similar to that solution, we can solve this by comparing the frequency of characters between both strings through a sliding window and a couple of hashmaps.  We will create a fixed set window the size of the substring, and we will continuously compare the hashmap of the substring character frequencies against the other string's hashmap of character frequencies.  If we have the same frequency between the two, we have an anagram in the string.

First off, if the substring is larger than the other string, then the string can't possibly contain an anagram of the substring.

In that case, we will return an empty array.

        if len(p) > len(s):
            return []

 

Next, we will create the two hashmaps for character frequencies between the two strings then our left and right pointers.

        p_chars, s_chars = {}, {}
        left, right = 0, 0

 

We will also create an array for storing the beginning index of each anagram, which we can get from the left pointer of our window later on.

        output = []

 

Afterward, we will push each character of the substring into the substring's frequency hashmap.

If the character is already there, we will just increment the frequency.

If not, we will initialize the frequency to once.

        for char in p:
            if char not in p_chars:
                p_chars[char] = 1
            else:
                p_chars[char] += 1

 

Then, we will push characters from the other string into its frequency hashmap, up to one place behind the size of the substring.

The reason being we will add that last character into our hashmap during our sliding window so that we can have an initial window size equal to the substring.  

The frequency incrementing process will be the same as the previous loop.

        while right < len(p)-1:
            if s[right] not in s_chars:
                s_chars[s[right]] = 1
            else:
                s_chars[s[right]] += 1
            right += 1

 

Now we will begin our sliding window.

        while right < len(s):

 

Just like other sliding window problems, our right pointer will be in charge of throwing values into the window.  The left will be in charge of evicting values from it.

Let's throw the character at the right pointer into the window.

            if s[right] not in s_chars:
                s_chars[s[right]] = 1
            else:
                s_chars[s[right]] += 1

 

If the string and substring's character frequencies match, we have a valid anagram.

If that is the case, we can append our left pointer to the output, since that is the start of the window and this anagram.

            if p_chars == s_chars:
                output.append(left)

 

We will need to evict the left pointer's character from the window and the string's hashmap if it's not the case.

We will do this by incrementing the frequency value, but we also need to check if that frequency is now zero.

If it is, we will delete that key from our hashmap.  If our window does come across an anagram later, we won't be able to tell because our hashmaps won't be equal, since that zero frequency character will still be in one of them.

            s_chars[s[left]] -= 1
            if s_chars[s[left]] == 0:
                del s_chars[s[left]]

 

Once we do that, we will continue moving our pointers down the string.

            left += 1
            right += 1

 

This isn't a traditional sliding window problem since our window is of a fixed size and it never expands or contracts, but we will continue moving along no matter what until we run out of characters.

After we have reached the end of the string, we will have a list of starting anagram indices within our output that we will return.

        return output