Find All Anagrams in a String

The problem description can be found in LeetCode.

Approach

This is a classic Sliding Window with a Static Size problem.

In fact, all we need to do is to keep track of a static window of size |p| by checking the characters of the string s.

Once the window with such size is completed, we can compare it with the counter of the string p. If they are equal, it means that we found a valid anagram.

Solution

from typing import List


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

        s_counter = self.get_default_counter()
        p_counter = self.get_chars_counter(p)
        ans = []
        left = 0

        for right, char in enumerate(s):
            s_counter[self.get_counter_idx(char)] += 1
            win_size = right - left + 1
            if win_size > len(p):
                s_counter[self.get_counter_idx(s[left])] -= 1
                left += 1

            if p_counter == s_counter:
                ans.append(left)

        return ans

    def get_default_counter(self) -> List[int]:
        return [0] * 26

    def get_counter_idx(self, char: str) -> int:
        assert isinstance(char, str)
        assert len(char) == 1
        assert "a" <= char <= "z"

        return ord(char) - ord("a")

    def get_chars_counter(self, s: str) -> List[int]:
        counter = self.get_default_counter()

        for char in s:
            counter[self.get_counter_idx(char)] += 1

        return counter

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the s string.