438. Find All Anagrams in a String

438. Find All Anagrams in a String

Question

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

Thinking:

• Method 1: HashMap

    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            Map<Character, Integer> map = new HashMap<>();
            for(char c : p.toCharArray()){
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            int pLen = p.length(), sLen = s.length();
            List<Integer> res = new ArrayList<>();
            if(sLen < pLen) return res;
            Map<Character, Integer> temp = new HashMap<>();
            for(int i = 0; i < pLen; i++){
                char c = s.charAt(i);
                temp.put(c, temp.getOrDefault(c, 0) + 1);
            }
            for(int i = pLen; i <= sLen; i++){
                if(check(temp, map)) res.add(i - pLen);
                // Remove the first character
                char first = s.charAt(i - pLen);
                Integer count = temp.get(first);
                if(count == 1) temp.remove(first);
                else if(count != null) temp.put(first, count - 1);
                if(i < sLen){
                    char c = s.charAt(i);
                    temp.put(c, temp.getOrDefault(c, 0) + 1);
                }
            }
            return res;
        }
        private boolean check(Map<Character, Integer> map1, Map<Character, Integer> map2){
            for(Map.Entry<Character, Integer> entry : map1.entrySet()){
                if(!map2.containsKey(entry.getKey())) return false;
                if(!map2.get(entry.getKey()).equals(entry.getValue())) return false;
            }
            return true;
        }
    }