LeetCode: Find All Anagrams in a String

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

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)