LeetCode: 76. Minimum Window Substring

First: O(N) solution.

However, is_satisfied function is not very efficient.

class Solution:
    def minWindow(self, s, t):
        ret = ''
        from collections import Counter
        c = Counter(t)
        chars = c.keys()
        j = 0
        for i, char in enumerate(s):
            if char in chars:
                c[char] -= 1
                if self.is_satisfied(c):
                    if not ret or (i - j + 1) <= len(ret):
                        ret = s[j:i+1]                    
                    while j <= i and self.is_satisfied(c):
                        if s[j] in chars:
                            c[s[j]] += 1
                        if not ret or (i - j + 1) <= len(ret):
                            ret = s[j:i+1]
                        j += 1
        return ret
                
    def is_satisfied(self, counter):
        for k, v in counter.items():
            if v > 0:
                return False
        return True

 

We can't check whether the substring satisfies the given condition with 'missing' variable.

class Solution:
    def minWindow(self, s, t):
        from collections import Counter
        need, missing = Counter(t), len(t)
        i, start, end = 0, 0, 0
        for j, char in enumerate(s, 1):
            if need[char] > 0:
                missing -= 1
            need[char] -= 1
            if missing == 0:
                while need[s[i]] < 0:
                    need[s[i]] += 1
                    i += 1
                if end == 0 or j - i < end - start:
                    end, start = j, i
                need[s[i]] += 1
                missing += 1
                i += 1
        return s[start:end]