# Wei-Lin Cheng  # 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 =  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.