438. Find All Anagrams in a String

// LeetCode URL: https://leetcode.com/problems/find-all-anagrams-in-a-string/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Sliding window
 *
 * Time Complexity: O(S + P)
 *
 * Space Complexity: O(P)
 *
 * S = Length of input string s. P = Length of input string p.
 */
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || p.length() == 0 || s.length() < p.length()) {
            return result;
        }

        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int start = 0;
        int end = 0;
        int toBeMatched = map.size();

        while (end < s.length()) {
            char endChar = s.charAt(end);
            if (map.containsKey(endChar)) {
                map.put(endChar, map.get(endChar) - 1);
                if (map.get(endChar) == 0) {
                    toBeMatched--;
                }
            }
            end++;

            while (toBeMatched == 0) {
                if (end - start == p.length()) {
                    result.add(start);
                }
                char startChar = s.charAt(start);
                if (map.containsKey(startChar)) {
                    if (map.get(startChar) == 0) {
                        toBeMatched++;
                    }
                    map.put(startChar, map.get(startChar) + 1);
                }
                start++;
            }
        }

        return result;
    }
}