[JAVA][75ms]Sliding Window + HashMap


  • 0
    K

    Typical sliding window template.

    while(window_end < boundary) {
      1)  process info at end;
      2)  Trigger the window check;
            If current window satisfy requirement:
                Record current window
            Remove start info from current window
            move start;
      3)move end;   
    }
    
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            if(s == null || p == null || s.length() == 0 || p.length() == 0) return res;
            
            Map<Character, Integer> ang = new HashMap<>();
            for(int i = 0; i < p.length(); i++) {
                char cur = p.charAt(i);
                if(!ang.containsKey(cur)) {
                    ang.put(cur, 1);
                } else {
                    ang.put(cur, ang.get(cur) + 1);
                }
            }
            
            // Create a new window(copy)
            Map<Character, Integer> window = new HashMap<>(ang);
            
            int start = 0;
            int end = start;
            int windowSize = p.length();
            
            while(end < s.length()) {
                
                char cur = s.charAt(end);
                
                // Need directly skip to current part.
                if(!ang.containsKey(cur)) {
                    start = ++end;
                    window = new HashMap<>(ang);
                    continue;
                }
                
                if(!window.containsKey(cur)) {
                    window.put(cur, -1);
                }else {
                    window.put(cur, window.get(cur) - 1);
                    if(window.get(cur) == 0) {
                        window.remove(cur);
                    }
                }
                
                if(end - start +1 == windowSize) {
                    if(window.size() == 0) {
                        res.add(start);
                    }
                    char startChar = s.charAt(start);
                    if(!window.containsKey(startChar)) {
                        window.put(startChar, 1);
                    } else {
                        window.put(startChar, window.get(startChar) + 1);
                    }
                    
                    if(window.get(startChar) == 0) {
                        window.remove(startChar);
                    }
                    start++;
                }
                end++;
            }
            return res;
        }
    

Log in to reply
 

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