438. Find All Anagrams in a String (Java, Sliding Window, Leetcode)

 

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        var list = new ArrayList<Integer>();
        if (s == null || p == null || s.length() == 0 || p.length() == 0) return list;
        
        //hashing
        //'a' is equal to 97 and 'z' is equal to 122.
        //constraints said that letters are always lower case.
        var hash = new int[128];
        
        for (char ch : p.toCharArray()) {
            hash[ch]++;
        }
        
        //two pointers and target length
        int left = 0, right = 0, count = p.length();
        
        //while fast pointer is less than the last index
        while (right < s.length()) {
            //if char has been cached, minus one of target length
            if (hash[s.charAt(right)] >= 1) count--;
            
            //always decrease the frequency of current fast pointer.
            hash[s.charAt(right)]--;
            //fast pointer always move no matter what.
            right++;
            
            //if all indices between two pointers are cached, add to answer.
            if (count == 0) list.add(left);
            
            //if we hit the limit(max length of sliding window), move the slow pointer.
            if (right - left == p.length()) {
                //anything not cached will be less than zero.
                //because we always decrease the frequency whenever fast pointer moves. no matter what it was cached or not.
                //so '>= 0' means it was cached originally.
                if (hash[s.charAt(left)] >= 0) count++;
                
                //increase the frequency of slow pointer.
                hash[s.charAt(left)]++;
                //only when we hit the limit, slow pointer moves.
                left++;
            }
        }
        return list;
    }
}

 

레퍼런스

https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92015/ShortestConcise-JAVA-O(n)-Sliding-Window-Solution 

Shortest/Concise JAVA O(n) Sliding Window Solution - LeetCode Discuss