438. Find All Anagrams in a String - cocoder39/coco39_LC GitHub Wiki

438. Find All Anagrams in a String

brute force: check each pair -> O(N) and check M times so O(M * N)

Optimization: first check O(N), then iterate through so O(M + N). As M > N so final time complexity is O(M)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        M, N = len(s), len(p)
        if M < N:
            return []

        p_bucket = [0 for _ in range(26)]
        for ch in p:
            p_bucket[ord(ch) - ord('a')] += 1

        s_bucket = [0 for _ in range(26)]
        for i in range(N):
            s_bucket[ord(s[i]) - ord('a')] += 1

        res = []
        if s_bucket == p_bucket:
            res.append(0)
        
        for i in range(1, M+1-N):
            s_bucket[ord(s[i-1]) - ord('a')] -= 1
            s_bucket[ord(s[i-1+N]) - ord('a')] += 1
            if s_bucket == p_bucket:
                res.append(i)
        return res