Problem Statement:

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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

Constraints:

1 <= s.length, p.length <= 3 * 10⁴
s and p consist of lowercase English letters.

Solution:

If we look at the frequency map of s or p, we know it is at max of length 26. So why not just match them? Beats 62% of all solutions in c++ with this simple logic. C++ Version:

 
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int ns = s.size(), np = p.size();
        if (ns<np) return {};
        vector<int> H_s(26,0), H_p(26,0);
        for (char ch: p) H_p[ch-'a']++;
        for (char ch: string(s.begin(),s.begin()+np)) H_s[ch-'a']++;
        vector<int> res;
        if (H_s==H_p) res.push_back(0);
        for (int i=1; i<=ns-np; i++)
        {
            char ch1 = s[i-1], ch2=s[i+np-1];
            H_s[ch1-'a']--;
            H_s[ch2-'a']++;
            if (H_s==H_p) res.push_back(i);
        }
        return res;
    }
};

Python version: (python has a collections.Counter that you can use to get frrequency map without writing code)

 
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
		if len(s)<len(p) return []
        H_p = collections.Counter(p)
        H_s = collections.Counter(s[:len(p)])
        res = []
        if H_s==H_p:
            res.append(0)
        for i in range(1,len(s)-len(p)+1):
            ch1, ch2 = s[i-1], s[i+len(p)-1]
            H_s[ch1]-=1
            H_s[ch2]+=1
            if H_s==H_p:
                res.append(i)
        return res

Complexity: O(26n) or in other words O(n)