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

Solution:

We put all elements from the patter string to a HashMap and count their frequencies.

Use a sliding window and count value to store the number of unique characters from the pattern string.

When traversing the source string s, if we find a character that exists in string p, we decrease its frequency in the HashMap.

If its frequency becomes 0, it means we found the same amount of such unique characters and we can decrease count by 1.

If we find count == 0, we found a match and check if the window size is a match.

Now add back the character in the beginning of the window.

If this character's frequency is larger than 0, we know we're lack of this character.

So we increase count by 1.



Code:

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