15ms beats 96% Java O(n) sliding window solution, with comments


  • 0
    O

    Used an extra map to track chars within window, update this map when an occurred char exceeds its counts, or reset this map when reading an alien char.

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            if (s == null || p == null || s.length() == 0 || p.length() == 0 || s.length() < p.length()) 
                return Arrays.asList();
            List<Integer> res = new ArrayList<Integer>();
            int len = p.length();
            int[] letters = new int[26];
            for (char c: p.toCharArray())
                letters[c - 'a']++;
            int[] map = Arrays.copyOf(letters, 26);
            int begin = 0, end = 0, count = 0;
            while (end < s.length()) {
                char cur = s.charAt(end);
                //reads a letter in p
                if (map[cur - 'a'] > 0) {
                    map[cur - 'a']--;
                    count++;
                    //finished all letters in p
                    if (len == count) {
                        res.add(begin);
                        map[s.charAt(begin) - 'a']++;
                        count--;
                        begin++;
                    }
                    end++;
                } else {
                	//reads a char in p, but exceeds
                	//move begin pointer to the next position of char
                	if (letters[cur - 'a'] > 0) {
                		while (s.charAt(begin) != cur) {
                			map[s.charAt(begin) - 'a']++;
                			count--;
                		}
                		begin++;
                		end++;
                	//read a char not in p
                	} else {
                		map = Arrays.copyOf(letters, 26);
                		end++;
                		begin = end;
                		count = 0;
                	}
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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