Problem description:

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 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:

Question to ask:

  1. what is anagram? size would be the same?

The idea is using fixed size sliding window, the size is len(p)
An anagram is frequency of each character should be same in two strings.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        pCount = Counter(p)
        sCount = Counter(s[:len(p)-1])
        res = []
        
        for end in range(len(p)-1, len(s)):
            sCount[s[end]] += 1
            if sCount == pCount:
                res.append(end-len(p)+1)
            
            start = end-len(p)+1
            sCount[s[start]] -= 1
            if sCount[s[start]] == 0:
                del sCount[s[start]]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.empty()) return {};
        vector<int> res, m(256, 0);
        for(auto c: p)
            m[c]++;
        
        int left= 0, right= 0, count= p.length();
        while(right< s.length()){
            //find a character in s that also appeared in p, then move right pointer and decrease the count
            //if a character is not in p, then the value will be negative
            if(m[s[right++]]-- >= 1) --count; 
            if(count == 0) res.push_back(left); //the starting index of the anagram
            
            /*
            an anagram's size would be the same as p.length()
            therefore, if length is equal, then we should move left pointer toward right 1 step
            if the value of character key in map is greater or equal then 0, it means it's a character in p
            because in previous step we minus 1 for all characters, so if a character in s is exists in p, then the value in map is at least 0
            */
            if(right-left == p.length() && m[s[left++]]++ >= 0) ++count;
        }
        return res;
    }
};

time complexity: $O(n)$

reference:
https://goo.gl/5yadmE
https://goo.gl/8XAyZH
https://goo.gl/gT32uu