Find All Anagrams in a String — LeetCode 438 Python Solution

The problem

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.

Example

Input

s = "cbaebabacd", p = "abc"

Output

[0,6]

Explanation

The substring with start index = 0 is "cba", which is an anagram of "abc".

Python solution

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

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 438. Find All Anagrams in a String is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems