438 Find All Anagrams in a String

Leetcode

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

使用一个数组计算匹配到 p 剩余每个元素的个数。使用 l 和 r 两个指针定一个一个窗口，如果右指针右边的字符需要匹配，则移动右指针并在数组中将相应的字符个数-1，否则移动左指针，将需要匹配的字符+1，如果左右指针长度相差 p 的长度，则说明所有字符都被匹配到，匹配次数+1

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list=new ArrayList<>();
        int[] sum=new int[26];
        for(char c:p.toCharArray()){
            sum[c-'a']++;
        }
        int l=0,r=-1;
        int lenP=p.length();
        int lenS=s.length();
        while(l<lenS){
            if(r-l+1==lenP){
                list.add(l);
            }
            
            if(r+1<lenS && sum[s.charAt(r+1)-'a']>0){
                sum[s.charAt(r+1)-'a']--;
                r++;
            } else {
                sum[s.charAt(l)-'a']++;
                l++;
            }
        }
        return list;
    }
}