Amazon-Find All Anagrams in a St

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

Solution:

public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res=new ArrayList<>();
        if(s==null||p==null||s.length()==0||p.length()==0) return res;
        int[] map=new int[256];
        for(char c:p.toCharArray()){
            map[c]++;
        }
        int left=0,right=0,count=p.length();
        while(right<s.length()){
            if(map[s.charAt(right++)]-->0){
                count--;
            }
            
            if(count==0) res.add(left);
            if(right-left==p.length()&&map[s.charAt(left++)]++>-1) count++;
        }
        return res;
    }

时间复杂度：O(n)
空间复杂度：O(1) [256]是常数级

滑动窗口算法类型题，核心思路是使用hash/map对p中字符计数，设立左、右指针组成滑动窗口，设置要匹配的字符数count=p.length()。遍历一遍s，右指针每次使用s中的字符，如果该字符hash/map值>0，代表该字符在p中存在，count--，无论是否匹配，对应的hash/map值都要减1。如果count==0，表示匹配成功，添加窗口左指针，代表匹配成功开始的索引。如果窗口大小是p.length()且左指针指向的字符是p中的字符，count++，无论判断情况，左指针加1，hash/map值加1，表示窗口的移动。