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:

思路与Leetcode 567: Permutation in string 一致。前者是找到了permutation就停止返回boolean；此题是需要全部遍历完目标string，找到所有的start indice.

Code:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        
        //Hashtable for tracking the occurance of charaters
        int[] tracker = new int[26];
        
        int sLen = s.length();
        int pLen = p.length();
        
        // corner case: s is empty or s is shorter than p
        if (sLen == 0 || sLen < pLen)
        {
            return result;
        }
        
        for (int i = 0; i < pLen; i++)
        {
            tracker [p.charAt(i) - 'a'] ++;
            tracker [s.charAt(i) - 'a'] --;
        }
        
        if (isAllZero (tracker))
        {
            result.add(0);
        }
        
        for (int i = pLen; i < sLen; i++)
        {
            tracker [s.charAt(i) - 'a'] --;
            tracker [s.charAt(i - pLen) - 'a'] ++;
            
            if (isAllZero (tracker))
            {
                result.add(i - pLen + 1);
            }
        }
        
        return result;
    }
    
    public boolean isAllZero (int [] tracker)
    {
        for (int entry : tracker)
        {
            if (entry != 0)
            {
                return false;
            }
        }
        
        return true;
    }
}