438_Find_All_Anagrams_in_a_String.java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92015/ShortestConcise-JAVA-O(n)-Sliding-Window-Solution
        List<Integer> list = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;
        int[] hash = new int[256]; //character hash
        //record each character in p to hash
        for (char c : p.toCharArray()) {
            hash[c]++;
        }
        //two points, initialize count to p's length
        int left = 0, right = 0, count = p.length();
        while (right < s.length()) {
            //move right everytime, if the character exists in p's hash, decrease the count
            //current hash value >= 1 means the character is existing in p
            if (hash[s.charAt(right++)]-- >= 1) count--; 
            //when the count is down to 0, means we found the right anagram
            //then add window's left to result list
            if (count == 0) list.add(left);
            //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window
            //++ to reset the hash because we kicked out the left
            //only increase the count if the character is in p
            //the count >= 0 indicate it was original in the hash, cuz it won't go below 0
            if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;
        }
        return list;
    }
    /*public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<Integer>();
        int ls = s.length(), lp = p.length();
        for (int i = 0; i <= ls - lp; i++) {
            boolean flag = true;
            String sub = s.substring(i, i + lp);
            int[] charCnt = new int[256];
            for (int j = 0; j < sub.length(); j++) {
                charCnt[sub.charAt(j)]++;
            }
            for (int j = 0; j < lp; j++) {
                charCnt[p.charAt(j)]--;
            }
            for (int j = 0; j < charCnt.length; j++) {
                if (charCnt[j] != 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                list.add(i);
            }
        }
        return list;
    }*/
}