Java Sliding Window. O(n). No need to loop 26 for each new window.


  • 1
    D

    Instead of looping through all 26 character for each shift, keep a set to hold all matched character. Deal with only head and tail of each new sliding window.

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<Integer>();
            if (s.length() < p.length()) {
                return res;
            }
            // get map of String p
            int[] pMap = new int[26];
            for (char c : p.toCharArray()) {
                pMap[c - 'a']++;
            }
            // get first map of String s.substring(0, p.length())
            int i = 0;
            int j = 0;
            int[] sMap = new int[26];
            for (; j < p.length(); j++) {
                sMap[s.charAt(j) - 'a']++;
            }
            // check if all 26 char matches
            Set<Character> matchSet = new HashSet<Character>();
            for (int k = 0; k < 26; k++) {
                if (pMap[k] == sMap[k]) {
                    matchSet.add((char) ('a' + k));
                }
            }
            if (matchSet.size() == 26) {
                res.add(0);
            }
            // now loop whole String s. each shift remove char[i] and add char[j]
            for (; j < s.length(); j++) {
                char c1 = s.charAt(i);
                sMap[c1 - 'a']--;
                char c2 = s.charAt(j);
                sMap[c2 - 'a']++;
                if (sMap[c1 - 'a'] == pMap[c1 - 'a']) {
                    matchSet.add(c1);
                } else if (matchSet.contains(c1)) {
                    matchSet.remove(c1);
                }
                if (sMap[c2 - 'a'] == pMap[c2 - 'a']) {
                    matchSet.add(c2);
                } else if (matchSet.contains(c2)) {
                    matchSet.remove(c2);
                }
                i++;
                if (matchSet.size() == 26) {
                    res.add(i);
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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