### 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 length of both strings **s** and **p** will not be larger than 20,100.

The order of output does not matter.

**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".
```

### Solution Thought Process

As we have to find a permutation of string `p`

, let's say that the length of `p`

is `k`

. We can say that we have to check every `k`

length subarray starting from 0. Let's say that length of `s`

is L.

Let's store all the frequencies in an `int remainingFrequency[26]={0}`

. Whenever we found an element we decrease it's remaining frequency.

The algorithm boils down to these step:

Check

`[0,k-1]`

- this k length window, check if all the entries in the remaining frequency are 0Check

`[1,k]`

- this k length window, check if all the entries in the remaining frequency are 0Check

`[2,k+1]`

- this k length window, check if all the entries in the remaining frequency are 0

.............................................................

.............................................................

- Check
`[windowStart+k-1, L-1]`

- this k length window, check if all the entries in the remaining frequency are 0

If the frequencies are 0, then we can say that this is a valid contender for our answer. For each window, we have to consider the `26`

values to determine if the window is an anagram.

So one thing we get hunch from here, this can be easily done in O(n) instead of any quadric time complexity.

**Why?**

When rolling over the next window, we can remove the leftmost element, and just add one right side element and add/decrease the remaining frequencies. For the leftmost element, we add the remaining frequency. For the rightmost element, we remove the remaining frequency. This is called the sliding window technique.

### Solution

```
class Solution {
private:
int remainingFrequency[26]={0};
bool checkFrequency(int *frequency)
{
for(int i=0;i<26;i++)
{
if(frequency[i]!=0)
{
return false;
}
}
return true;
}
public:
vector<int> findAnagrams(string s, string p) {
vector<int>result;
int remainingFrequency[26] = {0};
if(s.size()==0)
{
return result;
}
for(int i=0;i<p.size();i++)
{
remainingFrequency[p[i]-'a']++;
}
int windowStart=0;
int k=p.size();
for(int windowEnd=0;windowStart+k-1<s.size();windowEnd++)
{
remainingFrequency[s[windowEnd]-'a']--;
if(windowEnd>=k-1)
{
if(checkFrequency(remainingFrequency))
{
result.push_back(windowStart);
}
remainingFrequency[s[windowStart]-'a']++;
windowStart++;
}
}
return result;
}
};
```

### Complexity

**Time Complexity:** O(n)

**Space Complexity:** O(1)

## Top comments (0)