[LeetCode] 438. Find All Anagrams in a String

 Problem : https://leetcode.com/problems/find-all-anagrams-in-a-string/

Use sliding window approach. 

Time complexity =  O (M) + O (N). M = length of s. N = length of p.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> counter = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            counter.put(p.charAt(i), counter.getOrDefault(p.charAt(i), 0) + 1);
        }
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            counter.put(s.charAt(right), counter.getOrDefault(s.charAt(right), 0) - 1);
            while(left <= right && counter.get(s.charAt(right)) < 0) {
                counter.put(s.charAt(left), counter.get(s.charAt(left)) + 1);
                left += 1;
            }

            if (right + 1 - left == p.length()) {
                result.add(left);
            }
        }

        return result;
    }
}

Updated on 02/05/2023. Updated for a simplier sliding window solution which uses one hashmap to record the enoutered needed letters.