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
@ngaikw You are really polite and cultivated.
@ngaikw lol in computer science code judges
comparing constant length hashes at each iteration so each iteration is also O(1)
Can you explain a little bit why you're comparing two hashes here? What I see is comparison of two lists
shash and the time complexity of comparing two lists should be O(n).
@lizzy0127 Sure! So the runtime of iterating over a list depends on what the list contains. If we are iterating over a list that's given to us as the input, this would definitely be O(n). If we are iterating over a constant sized list, this is considered an O(1) operation. The two hashes we have here that we iterate over are constant sized.
he two lists sHash and pHash contain 123 elements
Why the two lists sHash and pHash contain 123 elements? How does this number (123) come from? Thanks!
@dhgtfui He might not need 123 elements, he only need a-zA-Z 52 elements in total
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.