438 Find All Anagrams in a String *****

sliding window module

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

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

            end++;
            while (count == 0) {
                System.out.println("end: " + end);
                char tempStart = s.charAt(start);
                if (map.containsKey(tempStart)) {
                    map.put(tempStart, map.get(tempStart) + 1);
                    if (map.get(tempStart) > 0) {
                        count++;
                    }
                }
                if (end - start == p.length()) {
                    ans.add(start);
                }
                start++;
            }
            // System.out.println("end" + end);
            // System.out.println("start" + start);
        }
        return ans;
    }
}