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

Thoughts

1. Two pointer to keep track of current sliding anagram candidate window

2. Find answers by tracking current sliding window status in the anagram map

3. Count: # character current sliding window needs (does not have)

Code: O(n)

class Solution {
    vector<int> answer;
public:
    vector<int> findAnagrams(string s, string p) {
        // first scaning throught p to construct char frequency map 
        unordered_map <char, int> map;

        for(int i = 0 ; i< p.length() ; i++){
           char key = p[i];
           ++map[key];
        }

        int left = 0, right = 0;
        int count = map.size(); // count how many char left to satisfy the anagram
        while(right < s.length()){
            char curChar = s[right];
            if(map.find(curChar) != map.end()){
                --map[curChar];
                if(map[curChar] == 0) count--; // means current sliding window already contains this character to fulfill the anagram 
            }
            right++;

            // count == 0 means there is a anagram in current sliding window,
            // we find them in the following code
            while(count == 0){
                // do 
                if(right - left == p.length()) answer.push_back(left); 

                // increment: change the count status for the next step
                char beginChar = s[left];
                if(map.find(beginChar) != map.end()){
                    // ++map[beginChar]; // for the next iteration;
                    if (++map[beginChar] > 0) count++; // means current sliding window needs this character to fulfill the anagram 
                }
                left++;
            }
        }

        return answer;
    }

};

Python

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        d = collections.Counter(p)
        slow,fast, res= 0, 0, []
        count = len(d)

        while fast < len(s):
            if s[fast] in d:
                d[s[fast]]-=1
                if d[s[fast]] == 0:
                    count -= 1
            fast += 1

            while count == 0:
                if fast - slow == len(p):
                    res.append(slow)
                if s[slow] in d:
                    d[s[slow]] +=1
                    if d[s[slow]] > 0:
                        count += 1

                slow += 1

        return res

C++ Template

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector <int> map (128, 0);
        int count = p.size(), slow = 0 , fast = 0;
        vector<int> res;
        for (auto c: p) ++map[c];
        while (fast < s.size()){
            if(map[s[fast++]]-- > 0) count--;
            while(count == 0){
                if(fast - slow == p.size()) res.push_back(slow);
                if (map[s[slow++]]++ == 0)count++;
            }
        }
        return res;
    }
};

Java Template

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int map [] = new int [128];
        int count = p.length(), slow = 0, fast = 0;

        List<Integer> res = new ArrayList<>();

        for (char c : p.toCharArray()) map[c] ++;

        char Chars [] = s.toCharArray();

        while(fast < Chars.length){
            if(map[Chars[fast++]]-- > 0) count--;

            while(count == 0){
                if(fast - slow == p.length()) res.add(slow);

                if(map[Chars[slow++]]++ == 0) count++;
            }
        }

        return res;
    }
}

Python Template

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        m = collections.defaultdict(int)
        cnt, slow, fast, res = len(p), 0, 0, []

        for c in p: m[c] +=1

        while fast < len(s):
            if(m[s[fast]] > 0):
                cnt-=1
            m[s[fast]] -=1 
            fast+=1

            while cnt == 0:
                if fast - slow == len(p): res.append(slow)

                if m[s[slow]] == 0:
                    cnt += 1
                m[s[slow]] += 1
                slow += 1

        return res

Special thanks: LeetCode Discussion Forum for the reference!