Find All Anagrams in a String

We can solve this problem by using a sliding window approach. The idea is to compare the frequency of characters in the pattern p with the frequency of characters in the current window of the string s. If the frequency counts match, then the current window is an anagram of the pattern.

Here are the detailed steps:

Calculate Pattern Frequency: Determine the frequency of characters in pattern p.
Initialize Window: Define a window of length equal to the length of p in string s.
Calculate Window Frequency: Determine the frequency of characters in the current window.
Check for Anagram: If the window frequency matches the pattern frequency, add the starting index of the window to the result.
Slide the Window: Move the window one character to the right, update the frequency counts, and repeat step 4.
Return Result: Return the list of starting indices that represent anagrams of pattern p in string s.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_length = len(p)
        s_length = len(s)
        if p_length > s_length:
            return []

        p_count = Counter(p)
        s_count = Counter(s[:p_length - 1])
        result = []

        for i in range(p_length - 1, s_length):
            # Add the new character to the current window
            s_count[s[i]] += 1
            
            # If counts match, then it's an anagram
            if s_count == p_count:
                result.append(i - p_length + 1)

            # Remove the leftmost character of the window
            left_char = s[i - p_length + 1]
            if s_count[left_char] == 1:
                del s_count[left_char]
            else:
                s_count[left_char] -= 1

        return result

Explanation:

We use the Counter class to maintain the frequency of characters in both pattern p and the current window of s.
The p_count represents the frequency of characters in p.
The s_count represents the frequency of characters in the current window of s.
We slide the window one character at a time, updating the frequency counts, and check if the counts match.
If the counts match, we add the starting index of the window to the result.

This algorithm works within the given constraints and has a time complexity of ( O(n) ), where ( n ) is the length of string s, since we are visiting each character in s exactly once.

Anagram:

A word, phrase, or name formed by rearranging the letters of another, such as

cinema iceman

An anagram is a word or phrase that when rearranged will create a new word or phrase. By definition, an anagram must have meaning (be a real word or phrase), but a permutation can be any ordering of the characters without needing to have meaning.

Example 2:

We don’t have to skip all the letters of the first anagram. We can skip only one letter (it does not matter whether it was part of the anagram or not)

If we encounter a ’d’ in example 2, we can slide the window start to start from after the ’d'

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# @param {String} s
# @param {String} p
# @return {Integer[]}
def find_anagrams(s2, s1)
    output = []
  goal = Array.new(26, 0)
  current = Array.new(26, 0)
    
  s1.chars.each do |c|
     goal[c.ord - 'a'.ord] += 1 
  end
    
  for i in (0...s2.size)
     current[s2[i].ord - 'a'.ord] += 1  
     
#      If the window size exceeds the size of s1
#       we need drop of the character leaving the window
     if i >= s1.size
        current_index = s2[i - s1.size]
        current[current_index.ord - 'a'.ord] -= 1
     end
      
     if goal == current
         output << (i - s1.size + 1)
     end
  end

    return output 
end