Sliding window and hashmap. O(n)


  • 1
    A

    To find all substrings which are anagrams we need to consider all substrings from s with length x = p.length. We can use sliding window approach to consider all substrings with length.
    Now the problem is to answer fastly to the question: is a substring is anagram of p. We can preliminary count the occurences of each character. While we will move sliding window we will decrease the counter for adding character and increase the counter for left character. Each time we should check wether the counter of all characters are 0 if so, we need to add that left position to the answer list.

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> anagrams = new ArrayList<Integer>();
            if (s==null || p==null) return anagrams;
            
            HashMap<Character, Integer> counter = getCounter(p);
            int len = p.length();
            for (int i =0; i<s.length(); i++) {
                if (i-len>=0) {
                    char prev = s.charAt(i-len);
                    counter.putIfAbsent(prev, 0);
                    counter.put(prev, counter.get(prev)+1);
                    if (counter.get(prev)==0) counter.remove(prev);
                }
                
                char cur = s.charAt(i);
                counter.putIfAbsent(cur, 0);
                counter.put(cur, counter.get(cur)-1);
                if (counter.get(cur)==0) counter.remove(cur);
                if (counter.isEmpty()) anagrams.add(i-len+1);
            }
            
            return anagrams;
        }
        
        private HashMap<Character, Integer> getCounter(String p) {
             HashMap<Character, Integer> counter = new HashMap<>();
             for (int i=0; i<p.length(); i++) {
                 char c = p.charAt(i);
                 counter.put(c, counter.getOrDefault(c, 0) + 1);
             }
             return counter;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.