438. Find All Anagrams in a String

notice:

// array compare
if (Arrays.equals(map, cMap)) {


// map compare
if (map.equals(cMap)) {

T: O(n*26)
S: O(26)

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        
        Map<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        int winsize = p.length();
        int left = 0;
        Map<Character, Integer> cMap = new HashMap<>();
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            cMap.put(c, cMap.getOrDefault(c, 0) + 1);
           
            if (right - left + 1 > winsize) {
                char lc = s.charAt(left);
                cMap.put(lc, cMap.getOrDefault(lc, 0) - 1);
                if (cMap.get(lc) == 0) {
                    cMap.remove(lc);
                }
                left++;
            }
            
            if (right - left + 1 == winsize) {
                if (map.equals(cMap)) {
                    res.add(left);
                }
            }
        }
        return res;
    }
}

/*
use sliding win with p's size

"cbaebabacd"
 [  ]
  [  ]
   [  ]

compare two hashmap each other is equal

T: O(n*26)
S: O(26)
*/

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        
        char[] map = new char[26];
        for (char c : p.toCharArray()) {
            map[c - 'a']++;
        }
        
        int winsize = p.length();
        int left = 0;
        char[] cMap = new char[26];
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            cMap[c - 'a']++;
           
            if (right - left + 1 > winsize) {
                char lc = s.charAt(left);
                cMap[lc - 'a']--;
                left++;
            }
            
            if (right - left + 1 == winsize) {
                if (Arrays.equals(map, cMap)) {
                    res.add(left);
                }
            }
        }
        return res;
    }
}

/*
use sliding win with p's size

"cbaebabacd"
 [  ]
  [  ]
   [  ]

compare two hashmap each other is equal

T: O(n*26)
S: O(26)
*/

same to 76, 567

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> needs = new HashMap<>();
        for (char c : p.toCharArray()) {
            needs.put(c, needs.getOrDefault(c, 0)+1);
        }
        int left = 0;
        int right = 0;
        int matched = 0;
        List<Integer> result = new ArrayList<>();
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            right++;
            if (needs.containsKey(rightChar)) {
                needs.put(rightChar, needs.get(rightChar)-1);
                if (needs.get(rightChar) == 0) {
                    matched++;
                }
            }
            while (matched == needs.size()) {
                if (right - left == p.length()) {
                    result.add(left);
                }
                char leftChar = s.charAt(left);
                left++;
                if (needs.containsKey(leftChar)) {
                    if (needs.get(leftChar) == 0) {
                        matched--;
                    }
                    needs.put(leftChar, needs.get(leftChar)+1);
                }
            }
        }
        return result;
    }
}
/*
"abab", p = "ab"
*/