438. Find All Anagrams in a String

Problem:

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

Analysis:
这道题用brute force做很简单。如果用sliding window做绝对不是esay。
Maintain a window with length of p's length. The task of the window is to find whether the elements in the window appears exactly the times as in p. So use the p's length as counter. If we meet a char in p decrease counter. When left is out of window and the char at left exists in p, we increase counter by one.

Solution：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length()) return res;
        int  k = p.length();
        int[] map = new int[256];
        for (char c: p.toCharArray()) {
            map[c]++;
        }
        int l = 0, r = 0, count = k;
        while (r < s.length()) {
            if (map[s.charAt(r++)]-- >= 1) {
                count--;
            }
            if (count == 0) res.add(l);
            // l exceeds window
            if (r - l == k && map[s.charAt(l++)]++ >= 0) count++;
        }
        return res;
    }

}