14. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. Strings consists of lowercase English letters only.

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: (Pattern matching but direct algorithms cannot be used)

Algorithm:

The idea is to use two count arrays: 1) The first count array store frequencies of characters in pattern. 2) The second count array stores frequencies of characters in current window of text.

class Solution
{
public:
    bool compare(vector<int> &pat, vector<int> &str)
    {
        for (int i = 0; i <= 25; i++)
        {
            if (pat[i] != str[i])
            {
                return false;
            }
        }
        return true;
    }
    
    vector<int> findAnaTime Complexity: O(n)grams(string s, string p)
    {
        vector<int> v;

        if (s == "" || p.length() > s.length())
        {
            return v;
        }
        
        // Arrays to maintain count of characters
        vector<int> pat(26);
        vector<int> str(26);
        for (int i = 0; i < p.length(); i++)
        {
            pat[p[i] - 97]++;
            str[s[i] - 97]++;
        }
        
        
        int l = p.length();
        for (int i = 0; i <= s.length() - l; i++)
        {
            //comparing two arrays
            if (compare(pat, str))
            {
                v.push_back(i);
            }
            // Removing prev char count
            str[s[i] - 97]--;
            
             // Increasing next char count
            if (i + l < s.length())
            {
                str[s[i + l] - 97]++;
            }
        }

        return v;
    }
};

Time Complexity: O(n)