Find All Anagrams in a String

anagram_indices_string.py

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


from collections import Counter


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        left = 0
        p_len = len(p)
        test_str_ctr = Counter()
        p_counter = Counter(p)
        start_idx_list = []
        for right, char in enumerate(s):
            distance = right - left + 1
            test_str_ctr[char] = test_str_ctr.get(char, 0) + 1
            # print(f"left={left} right={right} distance = {distance} test_str_ctr={test_str_ctr}")
            if distance == p_len and test_str_ctr == p_counter:
                start_idx_list += [left]
                # print(f"start_idx_list={start_idx_list}")
            if distance == p_len:
                last_char = s[left]
                test_str_ctr[last_char] -= 1
                if test_str_ctr[last_char] == 0:
                    test_str_ctr.pop(last_char)
                left += 1
        return start_idx_list