Find All Anagrams in a String

Problem Id: 438 Difficulty: Medium


Intuition

Solution


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []
        counts = {c:p.count(c) for c in string.ascii_lowercase if c in p}
        for c in s[:len(p) - 1]:
            if c in counts:
                counts[c] -= 1
                if counts[c] == 0:
                    counts.pop(c)
            else:
                counts[c] = -1

        ans = []
        for i in range(len(s) - len(p) + 1):
            c = s[i + len(p) - 1]
            if c in counts:
                counts[c] -= 1
                if counts[c] == 0:
                    counts.pop(c)
            else:
                counts[c] = -1

            if not counts:
                ans.append(i)

            c = s[i]
            if c in counts:
                counts[c] += 1
                if counts[c] == 0:
                    counts.pop(c)
            else:
                counts[c] = 1

        return ans