Find All Anagrams in a String

Question

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.

Solution

有個 general solution：Sliding Window Solution。參考以下 template：

    vector<int> map(128,0);
    int counter; // check whether the substring is valid
    int begin=0, end=0; //two pointers, one point to tail and one  head
    int d; //the length of substring

    for() { /* initialize the hash map here */ }

    while(end<s.size()){

        if(map[s[end++]]-- ?){  /* modify counter here */ }

        while(/* counter condition */){ 

             /* update d here if finding minimum*/

            //increase begin to make it invalid/valid again

            if(map[s[begin++]]++ ?){ /*modify counter here*/ }
        }  

        /* update d here if finding maximum*/
    }
    return d;

public List<Integer> findAnagrams(String s, String p) { 
        List<Integer> list = new ArrayList<>();
        if(s == null || s.length() == 0 || p == null || p.length() == 0) return list;
        int[] hash = new int[256];
        for(char c : p.toCharArray()){
            hash[c]++;
        }

        int left = 0, right = 0, count = p.length();
        while(right < s.length()){
            if(hash[s.charAt(right++)]-- >= 1) count--;
            if(count==0) {
                list.add(left);
            }
            if(right-left==p.length() && hash[s.charAt(left++)]++ >= 0) {
                count++;
            }
        }
        return list;
    }