[Leetcode] 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".

Analysis:

One intuitive solution is to iterate all the substring of length p.length() and compare whether the substring is an anagram of p by sorting both substring and p and compare. Unfortunately, it will be time out for big data set since the running time would be O(n*n*klog(k) where n is the length of s and k is the length of p.

Think again how we know two strings are the anagram: we can either sort the two string, or we can count each letters of the string and compare whether the count of each letters are equal. So, for s, we first get the count of each letter of the substring of first p.length() characters.Then, whenever move a letter forward one letter,  we just need to change the count by removing 1 count of the first letter and adding 1 count of the last letter. The running time would be O(n+k) since equals function takes constant time. 

    boolean equals(int[] a, int[] b) {
        for(char c = 'a'; c<='z'; c++) {
            if (a[c] != b[c])
                return false;
        }
        return true;
    }
    
    public List<Integer> findAnagrams(String s, String p) {
        int[] pCount = new int[256];
        for(char c: p.toCharArray())
            pCount[c]++;
            
        int[] sCount = new int[256];
        for(int i=0; i<p.length() && i < s.length(); i++)
            sCount[s.charAt(i)]++;
        
        List<Integer> list = new ArrayList<>();
        if (equals(pCount, sCount))
            list.add(0);
        
        for(int i= p.length(); i < s.length(); i++) {
            sCount[s.charAt(i)]++;
            sCount[s.charAt(i-p.length())]--;
            if (equals(pCount, sCount))
                list.add(i-p.length() + 1);
        }
        return list;
    }