438. Find All Anagrams in a String

Description:

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.

'''
[1] sliding window and hashmap) # optimization required

idea::
pMap contains every frequency of all character in p
while sliding window, store the index if the element is the same as pMap

code::
def findAnagrams(self, s: str, p: str) -> List[int]:
    # edge case
    if len(s)<len(p):
        return []

    # p hashmap
    pMap=[0 for _ in range(len(string.ascii_lowercase))]
    for c in p:
        pMap[ord(c)-ord('a')]+=1

    # window
    window=[0 for _ in range(len(pMap))]

    # sliding
    ans=[]
    isFirst=True
    for i in range(0,len(s)-len(p)+1):
        if isFirst:
            for j in range(len(p)):
                window[ord(s[j])-ord('a')]+=1
            isFirst=False
        else:
            window[ord(s[i-1])-ord('a')]-=1
            window[ord(s[i+len(p)-1])-ord('a')]+=1
        if self.isAnagram(window,pMap):
            ans.append(i)
    return ans

def isAnagram(self,window,pMap):
    for i in range(len(string.ascii_lowercase)):
        if window[i]!=pMap[i]:
            return False
    return True
    
-T/C: O(m+(n-m))==O(n) # n==len(s), m==len(p)
-S/C: O(26)==O(1)
'''

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # edge case
        if len(s)<len(p):
            return []
        
        # p hashmap
        pMap=[0 for _ in range(len(string.ascii_lowercase))]
        for c in p:
            pMap[ord(c)-ord('a')]+=1
            
        # window
        window=[0 for _ in range(len(pMap))]
        
        # sliding
        ans=[]
        isFirst=True
        for i in range(0,len(s)-len(p)+1):
            if isFirst:
                for j in range(len(p)):
                    window[ord(s[j])-ord('a')]+=1
                isFirst=False
            else:
                window[ord(s[i-1])-ord('a')]-=1
                window[ord(s[i+len(p)-1])-ord('a')]+=1
            if self.isAnagram(window,pMap):
                ans.append(i)
        return ans
            
    def isAnagram(self,window,pMap):
        for i in range(len(string.ascii_lowercase)):
            if window[i]!=pMap[i]:
                return False
        return True