Maintain a window of len(p) in s, and slide to right until finish. Time complexity is O(len(s)).
from collections import Counter def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ res =  pCounter = Counter(p) sCounter = Counter(s[:len(p)-1]) for i in range(len(p)-1,len(s)): sCounter[s[i]] += 1 # include a new char in the window if sCounter == pCounter: # This step is O(1), since there are at most 26 English letters res.append(i-len(p)+1) # append the starting index sCounter[s[i-len(p)+1]] -= 1 # decrease the count of oldest char in the window if sCounter[s[i-len(p)+1]] == 0: del sCounter[s[i-len(p)+1]] # remove the count if it is 0 return res
@weijuemin Nope... because OJ already imports everything. On local machine, you should put
from collections import Counter in the beginning.
@WKVictor Hmmm odd. I had to import Counter on OJ otherwise I'm getting this NameError. Not sure what's going on behind the scene. Well, just a friendly reminder in case you forgot but seems you didn't have the same issue I got so never mind :-)
@Zura Because the window will be slided to right by one position in next iteration, the oldest char will no longer be in the window.
@weijuemin adding from collections import Counter would resolve the issue.
@WKVictor I thought it was an redundant operation(because you can just delete it ) but then I realized that there could be multiple same character in the Counter. Thanks for your explanation.
What is the time complexity of "sCounter == pCounter"? Could it be O(len(p)) in worst case?
@tototo I concern it as well
@tototo However, I used the solution to avoid use "=" on Counter and it is even slower.
@tototo Thank you. I updated the complexity to O(len(s)*len(p))
def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ d = defaultdict(int) ns, np = len(s), len(p) ans =  for c in p: d[c] -= 1 for i in xrange(ns): if i < np: d[s[i]] += 1 if not d[s[i]]: del d[s[i]] else: if not d: ans.append(i-np) d[s[i-np]] -= 1 if not d[s[i-np]] : del d[s[i-np]] d[s[i]] += 1 if not d[s[i]]: del d[s[i]] if not d: ans.append(i-np+1) return ans
Time complexity can be reduced down to O(len(s)) if you use a dictionary instead of a Counter. Same idea, just keep a sliding window and delete the keys when they reach zero. But, there's no need for Counter comparison (which is O(len(p)), since you can just check if the dictionary is empty.
@david120 this code is extremely unreadable, but the idea is great!
@tototo In fact, since there are at most 26 English letters, pCounter can have at most 26 keys, which implies the comparison "sCounter == pCounter" is actually O(1). So I change the time complexity back to O(len(s)).
@WKVictor Thanks you very much!
Did it using a while loop, thought it was more intuitive.
def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ a= l=len(p) cp=Counter(p) cs=Counter(s[:l-1]) i=0 while i+l<=len(s): cs[s[i+l-1]]+=1 if cs==cp: a.append(i) cs[s[i]]-=1 if cs[s[i]]==0: del cs[s[i]] i+=1 return a
I have a question for the dictionary. Based on sub list, you create a sCounter. In for loops, sCounter[s[i]] += 1. What if s[i] is not a key in the sCounter? It will raise an error.
@TQINSYR No, it will not raise a keyerror. It has a default value 0 for non-existing key. Try this: s = Counter(), s['c'] will output 0.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.