Find All Anagrams in a String

Given a stringsand anon-emptystringp, find all the start indices ofp's anagrams ins.

Strings consists of lowercase English letters only and the length of both stringssandpwill 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".

Tips:

需要一个map来存放字母出现的次数，加上头尾指针start和end。不断更新start和end直到end达到s的末尾，更新map中出现字母的次数和计数器count。如果end - start = p.length(), 则更新start。

复杂度：O(n)

Code:

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return res;
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, end = 0;
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int count = 0;
        while (end < s.length()) {
            map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) - 1);
            if (map.get(s.charAt(end)) >= 0) count++;
            if (count == p.length()) res.add(start);
            end++;
            if (end - start == p.length()) {
                if (map.get(s.charAt(start)) >= 0) count--;
                map.put(s.charAt(start), map.get(s.charAt(start)) + 1);
                start++;
            }
        }
        return res;
    }
}