# Find All Anagrams in a String

##### January 21, 2024

## Problem Statement #

Given a string `s`

and a non-empty string `p`

, find all the start indices of `p`

’s anagrams in `s`

. Strings consist of lowercase English letters only and the order of output does not matter.

**Example**:

- 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”, also an anagram of “abc”.

## Solution Approach #

The solution uses the sliding window approach combined with a hashmap to track the frequency of characters in `p`

and the current window in `s`

.

## Algorithm Steps #

- Create two hashmaps to store the frequency of characters in
`p`

and the current window in`s`

. - Use a sliding window of size equal to the length of
`p`

to traverse`s`

. - Update the frequency of characters in the current window.
- If the two hashmaps are equal, add the start index of the window to the result list.
- Continue sliding the window and updating the frequency hashmap.
- Return the list of start indices.

## Code (Python) #

```
from collections import Counter
def findAnagrams(s, p):
if len(p) > len(s): return []
p_count = Counter(p)
s_count = Counter(s[:len(p) - 1])
result = []
for i in range(len(p) - 1, len(s)):
s_count[s[i]] += 1 # Add the current character to the window
if s_count == p_count:
result.append(i - len(p) + 1) # Append the start index of the window
s_count[s[i - len(p) + 1]] -= 1 # Remove the character left out of the window
if s_count[s[i - len(p) + 1]] == 0:
del s_count[s[i - len(p) + 1]]
return result
# Test the function
print(findAnagrams("cbaebabacd", "abc")) # Output: [0, 6]
```

## Time Complexity #

O(n), where n is the length of string `s`

. Each character in `s`

is processed once.

## Space Complexity #

O(1), as the hashmaps store a maximum of 26 English lowercase letters.