0438 - Find All Anagrams in a String

0438 - Find All Anagrams in a String

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.

Examples

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".

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".

Constraints

1 <= s.length, p.length <= 3 * 104 s and p consist of lowercase English letters.

Java Solution

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if(p.length() > s.length()) return result;
        
        int[] sMap = new int[26];
        int[] pMap = new int[26];
        
        for(int i = 0; i < p.length(); i++) {
            pMap[(int) (p.charAt(i) - 'a')]++;
        }
        
        for(int i = 0; i < s.length(); i++) {
            sMap[(int) (s.charAt(i) - 'a')]++;
            
            if(i >= p.length()) sMap[(int) (s.charAt(i-p.length()) - 'a')]--;
            
            if(Arrays.equals(sMap, pMap)) result.add(i - p.length() + 1);
        }
        
        return result;
    }
}