LeetCode: Find All Anagrams in a String
Tags: leetcode, datastructures, algorithms, slidingwindow
Published: 2020-05-19 21:23:28

---
title: LeetCode: Find All Anagrams in a String
published: true
description: Day 17
tags: leetcode, datastructures, algorithms, slidingwindow
series: LeetCode May Challenge
---
### 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 0

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

- Check `[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

```c++
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)