Day 29: Find All Anagrams in a String : Sliding Window - leetcode - Python3

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.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

• 1 <= s.length, p.length <= 3 * 104
• s and p consist of lowercase English letters.

SOLUTION

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)

        result = [0] if pCount == sCount 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:

                result.append(l)

        return result

Time Complexity: O(s)

Space Complexity:O(1)

How it works:

1. The function first checks if the length of the pattern is longer than the string. If it is, then there can be no anagrams, so the function returns an empty list.
2. The function then creates two dictionaries to store the counts of each character in the pattern and the string.
3. The function then checks if the two dictionaries have the same counts for each character. If they do, then the function knows that the string contains an anagram of the pattern.
4. The function then initializes two pointers, a left pointer and a right pointer. The left pointer will start at the beginning of the string, and the right pointer will start at the end of the pattern.
5. The function then iterates from the right pointer to the end of the string.
6. At each step, the function increments the count of the character at the right pointer in the string count dictionary.
7. The function then decrements the count of the character at the left pointer in the string count dictionary.
8. If the count of the character at the left pointer becomes 0, the function removes it from the dictionary.
9. The function then checks if the string count dictionary now has the same counts as the pattern count dictionary. If it does, then the function knows that the string contains an anagram of the pattern.
10. The function then appends the index of the left pointer to a list.
11. The function then increments the left pointer by 1.
12. The function repeats steps 5-11 until the right pointer reaches the end of the string.
13. The function then returns the list of indices where the substrings are anagrams of the pattern.