Hash the number of times each character appears in p. Iterate over s with a sliding window and maintain a similar hash. If these two hashes are ever the same, add that to the result.
Each of the hashes have a finite (a-z, A-Z) number of possible characters, so the space used is O(1)
We iterate over s linearly, comparing constant length hashes at each iteration so each iteration is also O(1), so the runtime is O(n)
class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ res =  n, m = len(s), len(p) if n < m: return res phash, shash = *123, *123 for x in p: phash[ord(x)] += 1 for x in s[:m-1]: shash[ord(x)] += 1 for i in range(m-1, n): shash[ord(s[i])] += 1 if i-m >= 0: shash[ord(s[i-m])] -= 1 if shash == phash: res.append(i - m + 1) return res
yes indeed! The two lists sHash and pHash contain 123 elements, one for each ASCII value from the strings s and p. This is a really cool way to count the frequency of each letter in the string. I also loved the efficiency of adding a single letter to sHash, and then checking whether the sHash ==pHash.
@ZhengwuFang Your English is really bad man
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.