Python Sliding Window Solution using Counter


  • 11
    W

    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
    

  • 0
    W

    Did you have a "NameError: global name 'Counter' is not defined" error?


  • 0
    W

    @weijuemin Nope... because OJ already imports everything. On local machine, you should put from collections import Counter in the beginning.


  • 0
    W

    @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 :-)


  • 0

    why do you decrease the count of oldest char in the window?


  • 1
    W

    @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.


  • 0
    S

    @weijuemin adding from collections import Counter would resolve the issue.


  • 0

    @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.


  • 0
    T

    What is the time complexity of "sCounter == pCounter"? Could it be O(len(p)) in worst case?


  • 0
    D

    @tototo I concern it as well


  • 0
    D

    @tototo However, I used the solution to avoid use "=" on Counter and it is even slower.


  • 0
    W

    @tototo Thank you. I updated the complexity to O(len(s)*len(p))


  • 0
    D
    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.


  • 0
    M

    @david120 this code is extremely unreadable, but the idea is great!


  • 0
    W

    @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)).


  • 0

    @WKVictor Thanks you very much!


  • 2
    L

    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

  • 0
    T

    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.


  • 0
    W

    @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.


  • 0
    F

    why is

    if sCounter[s[i-len(p)+1]] == 0:
                    del sCounter[s[i-len(p)+1]]   # remove the count if it is 0
    

    necessary??


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.