76. Minimum Window Substring

Tags:

• Hard
• slide window
• hash
• recommend

Link

Slide window with hash

This pattern is basic for many other extend questions.

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

        CT = Counter(t)

        S = set(CT.keys())
        MT = defaultdict(int)

        res = ""
        count = 0

        l = 0
        for i, c in enumerate(s):
            if c in S:
                MT[c] += 1
                if MT[c] == CT[c]:
                    count += 1

            if count == len(S):
                while count == len(S):
                    if s[l] in S:
                        MT[s[l]] -= 1
                        if MT[s[l]] == CT[s[l]] -1:
                            count -= 1
                    l+=1

                if not res:
                    res = s[l-1:i+1]
                elif i - l + 1 < len(res):
                    res = s[l-1:i+1]

        return res