438. Find All Anagrams in a String - Explanation

1. Brute Force

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        p = sorted(p)
        res = []
        for i in range(n - m + 1):
            sub = sorted(s[i : i + m])
            if sub == p:
                res.append(i)
        return res

Time & Space Complexity

Time complexity: $O(n * m \log m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the length of the string $p$ .

2. Prefix Count + Sliding Window

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        if m > n:
            return []
        pCount = [0] * 26
        for c in p:
            pCount[ord(c) - ord('a')] += 1

        prefix = [[0] * 26 for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(26):
                prefix[i][j] = prefix[i - 1][j]
            prefix[i][ord(s[i - 1]) - ord('a')] += 1

        i, j = 0, m - 1
        res = []
        while j < n:
            isValid = True
            for c in range(26):
                if prefix[j + 1][c] - prefix[i][c] != pCount[c]:
                    isValid = False
                    break
            if isValid:
                res.append(i)
            i += 1
            j += 1

        return res

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ and $m$ is the length of the string $p$ .

3. Sliding Window

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s): return []
        pCount, sCount = {}, {}
        for i in range(len(p)):
            pCount[p[i]] = 1 + pCount.get(p[i], 0)
            sCount[s[i]] = 1+ sCount.get(s[i], 0)

        res = [0] if sCount == pCount else []
        l = 0
        for r in range(len(p), len(s)):
            sCount[s[r]] = 1+ sCount.get(s[r], 0)
            sCount[s[l]] -= 1

            if sCount[s[l]] == 0:
                sCount.pop(s[l])
            l += 1
            if sCount == pCount:
                res.append(l)
        return res

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of the string $s$ and $m$ is the length of the string $p$ .

4. Sliding Window (Optimal)

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

        pCount = [0] * 26
        sCount = [0] * 26
        for i in range(m):
            pCount[ord(p[i]) - ord('a')] += 1
            sCount[ord(s[i]) - ord('a')] += 1

        match = sum(1 for i in range(26) if pCount[i] == sCount[i])
        res = []
        if match == 26:
            res.append(0)

        l = 0
        for r in range(m, n):
            c = ord(s[l]) - ord('a')
            if sCount[c] == pCount[c]:
                match -= 1
            sCount[c] -= 1
            l += 1
            if sCount[c] == pCount[c]:
                match += 1

            c = ord(s[r]) - ord('a')
            if sCount[c] == pCount[c]:
                match -= 1
            sCount[c] += 1
            if sCount[c] == pCount[c]:
                match += 1

            if match == 26:
                res.append(l)

        return res

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of the string $s$ and $m$ is the length of the string $p$ .