This article includes the code implementation in Python, a detailed explanation, and the complexity analysis for LeetCode - 438. Find All Anagrams in a String. Please hit the like button if you find this article is helpful. I will keep writing LeetCode solutions.

Explanation

Intuition

To check whether two strings are anagram, one easy way is to count how many unique characters these two strings have and check if they share the same counts.

For this question, the brute force solution is to build hash maps for every substring with the length of string p from string s and check if they share the same character counts. And it leads to time complexity: m * n where m is the length of string p and n is the length of string s because you need to build up the hash map of character counts when you traverse all the substring with the length of string p from string s.

To improve the time complexity, you can use the sliding window technique to just update the existing hash map of character counts from the last substring of string s instead of building up a new one.

Example

Assume the length of string p is 2, for the first iteration, you build up a hash map for substring from index 0 to index 1 if you start from index 0. For the second iteration, you don't need to build up a new hash map for substring from index 1 to index 2. You just need to decrease the character count for the character on index 0 and increase the character count for the character on index 1. Then you keep doing this until you reach the end of string s. One thing you need to pay attention to is that you need to remove the key from the hash map if such key's value reaches 0 or the hash map comparison would fail.

Input: s = "abcb", p = "ab"

The substring with start index = 0 is "ab", sCount = {"a":1, "b":1}, same as pCount = {"a":1, "b":1}.

The substring with start index = 1 is "bc", decrease sCount["a"] by 1 and remove it from the hash map, increase sCount["c"] by 1, sCount = {"b":1, "c":1}.

The substring with start index = 2 is "ab", decrease sCount["b"] by 1, increase sCount["b"] by 1, sCount = {"b":1, "c":1}.

Code Implementation in Python

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]] = pCount.get(p[i], 0) + 1
            sCount[s[i]] = sCount.get(s[i], 0) + 1

        result = [0] if pCount == sCount else []

        l, r = 0, len(p)
        while r < len(s):
            sCount[s[r]] = sCount.get(s[r], 0) + 1
            sCount[s[l]] -= 1
            if sCount[s[l]] == 0:
                sCount.pop(s[l])
            l, r = l + 1, r + 1
            if sCount == pCount:
                result.append(l)

        return result

Complexity Analysis

O(26n) time | O(52) space

Since the input strings s and p only consist of lowercase English letters, the maximum number of keys in the hash map is 26. n is the length of the input string s. Each time we compare the two hash maps, we only need to compare it 26 times for the worst case.