Python minimum window using Counter


  • 0
    P
    from collections import Counter
    class Solution(object):
        def minWindow(self, s, t):
            if not s or not t or len(t) > len(s):
                return ""
    
            chars, count, min_size, min_start = Counter(t), len(t), float('inf'), -1
            l = r = 0
    
            for r in range(len(s)):
                # for the char which is also present in t, we decrement total count
                if chars[s[r]] >= 1:
                    count -= 1
                # we just decrement count for every char
                chars[s[r]] -= 1
    
                while l<len(s) and count == 0:
                    if chars[s[l]] >= 0:
                        # window is not valid any more once this char is removed
                        if r-l+1 < min_size:
                            min_size = r-l+1
                            min_start = l
                        count += 1
                    # we increment number of occurences for every char    
                    chars[s[l]] += 1
                    l += 1
    
            return s[min_start:min_start+min_size] if min_start > -1 else ""
    
    

Log in to reply
 

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