438. Find All Anagrams in a String

三刷 06/2022

Version #1 Sliding Window

Time O(N) - N is the length of the longer string

Space O(26) ~ O(1)

Runtime: 10 ms, faster than 82.16% of Java online submissions for Find All Anagrams in a String.

Memory Usage: 48.1 MB, less than 46.53% of Java online submissions for Find All Anagrams in a String.

class Solution {

    public List<Integer> findAnagrams(String s, String p) {

        int[] count = new int[26];

        for (int i = 0; i < p.length(); i++) {

            count[p.charAt(i) - 'a']++;

        }

        List<Integer> result = new ArrayList<>();

        int matchCount = 0;

        int start = -1;

        // (start, end]

        for (int end = 0; end < s.length(); end++) {

            int index = s.charAt(end) - 'a';

            count[index]--;

            if (count[index] >= 0) {

                matchCount++;

            }

            while (count[index] < 0) {

                start++;

                int sIndex = s.charAt(start) - 'a';

                count[sIndex]++;

                if (count[sIndex] > 0) {

                    matchCount--;

                }

            }

            if (matchCount == p.length()) {

                result.add(start + 1);

            }

        }

        return result;

    }

}

“while (right < s.length()) {
//move right everytime, if the character exists in p's hash, decrease the count //current hash value >= 1 means the character is existing in p if (hash[s.charAt(right++)]-- >= 1) count--; //when the count is down to 0, means we found the right anagram //then add window's left to result list if (count == 0) list.add(left); //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window //++ to reset the hash because we kicked out the left //only increase the count if the character is in p //the count >= 0 indicate it was original in the hash, cuz it won't go below 0 if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;  }”

一刷
注意counter数的是需要的char个数
如果char不在target里面，那么右指针-1左指针+1，两者只会互相抵消 永远不会大于0
只有当left扫过大于0的才是曾经存在于target里面的char，才能影响counter
95.80 %

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return result;
        //only lowercase letters
        int[] hash = new int[26];
        int counter = 0; //keep track of #desired letters
        int index;
        //Generate the original count of each char
        for (int i = 0; i < p.length(); i++) {
            index = p.charAt(i) - 'a';
            hash[index]++;
            counter++;
        }
        int left = 0, right = 0;
        while (right < s.length()) {
            index = s.charAt(right++) - 'a';
            if (--hash[index] >= 0) {
                counter--;
            }
         
            while (counter == 0) {
                if ((right - left) == p.length()) {
                    result.add(left);
                }
                index = s.charAt(left++) - 'a';
                if (++hash[index] > 0) counter++;
            }
        }
        return result;
    }
}

二刷
88.62 %
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null) return null;
        List<Integer> result = new ArrayList<>();
        int pLength = p.length();
     
        int[] counter = new int[26];
        int match = 0;
        for (int i = 0; i < pLength; i++) {
            counter[p.charAt(i) - 'a']++;
            match++;
        }
        // [left, right] ->  right - left + 1 == pLength -> remove left
        //s . . . . . .
        int left = 0, right = 0;
        for (right = 0; right < s.length(); right++) {
            if (--counter[s.charAt(right) - 'a'] >= 0) match--;
            if (match == 0) result.add(left);
            if (right - left + 1 == pLength) {
                if (++counter[s.charAt(left) - 'a'] > 0) match++;
                left++;
            }
        }
        return result;
    }
}