Leetcode/亚麻 -- 438. Find All Anagrams in a String (window2ptr)

438. Find All Anagrams in a String(window 2ptr)
easy
https://leetcode.com/problems/find-all-anagrams-in-a-string/

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

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".

思路： string window套路 using 2 pointer, key is to check 'end - start + 1 == t.length()' to find valid anagram.
Complexity: O(N) time - loop, O(N) space - map

public class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        List<Integer> res = new ArrayList<Integer>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();//<all char, freq in t>
        for(char c : s.toCharArray()) map.put(c, 0);
        for(char c : t.toCharArray()){
            if(map.containsKey(c))
                map.put(c, map.get(c) + 1);
            else 
                return res;
        }
        int start = 0, end = 0;
        int counter = t.length();
        while(end < s.length()){
            char cur = s.charAt(end);
            if(map.get(cur) > 0) counter--;
            map.put(cur, map.get(cur) - 1);
            while (counter == 0){
                if(end - start + 1 == t.length()) res.add(start);
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) + 1);
                if(map.get(c2) > 0) counter++;
                start++;
            }
            end++;
        }
        return res;
    }
}