Minimum Window Substring

PHOTO EMBED

Sat Mar 16 2024 22:55:12 GMT+0000 (Coordinated Universal Time)

Saved by @playadust

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        
        counts = Counter(t)

        def contains():
            return sum([x>0 for x in counts.values()]) == 0

        l = 0
        res = ""
        size = float('INF')
        for r in range(len(s)):
            if s[r] in counts:
                counts[s[r]] -= 1
                # print("R: ", s[r], counts)
                while l <= r and contains():
                    if contains() and r-l+1 < size:
                        size = r-l+1
                        res = s[l:r+1]
                    # print("record res:", res)
                    if s[l] in counts:
                        counts[s[l]] += 1
                        # print("remove L: ", s[l], counts, s[l:r+1])
                    l += 1
        return res


content_copyCOPY