Find All The Anagrams in a String

Problem Statement:

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = “cbaebabacd”, p = “abc” Output: [0,6] Explanation: The substring with start index = 0 is “cba”, which is an anagram of “abc”. The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example 2:

Input: s = “abab”, p = “ab” Output: [0,1,2] Explanation: The substring with start index = 0 is “ab”, which is an anagram of “ab”. The substring with start index = 1 is “ba”, which is an anagram of “ab”. The substring with start index = 2 is “ab”, which is an anagram of “ab”.

Constraints:

• 1 <= s.length, p.length <= 3 * 10^4
• s and p consist of lowercase English letters.

Solution:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int windowSize = p.length();
        int start = 0;
        int end = 0;
        int size = s.length();
        List<Integer> indices = new ArrayList<>();
        
        HashMap<Character, Integer> sMap = new HashMap<>();
        
        HashMap<Character, Integer> pMap = new HashMap<>();
        for(Character ch: p.toCharArray()){
            pMap.put(ch, pMap.getOrDefault(ch, 0) + 1);
        }
 
        while(end < size){
            sMap.put(s.charAt(end), sMap.getOrDefault(s.charAt(end), 0) + 1);
            
            if(windowSize == end - start + 1){
                if(sMap.equals(pMap)){
                    indices.add(start);
                }
                
                sMap.put(s.charAt(start), sMap.getOrDefault(s.charAt(start), 0) - 1);
                sMap.remove(s.charAt(start), 0);
                start++;
            }
            end++;
        }
        return indices;
    }
}