76. Minimum Window Substring

Hard

Problem:

Receive strings S and T as input and find the smallest window in S that contains all characters of T in $O(n)$ time complexity.

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

https://leetcode.com/problems/minimum-window-substring/

Solution:

This can be solved using the two-pointer technique which tightens the size of the left and right pointers when the appropriate position is found, while moving the sliding window to the right continuously.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""

        # HashMap
        countT = collections.Counter(t)
        window = {}

        have, need = 0, len(countT)
        res, resLen = [-1, -1], float("inf")
        left = 0

        for right in range(len(s)):
            c = s[right]
            window[c] = 1 + window.get(c, 0)

            # Only count if the character is in t
            if c in countT and window[c] == countT[c]:
                have += 1

            while have == need:
                # update our result
                if (right - left + 1) < resLen:
                    res = [left, right]
                    resLen = right - left + 1
                # pop from the left of our window
                window[s[left]] -= 1
                if s[left] in countT and window[s[left]] < countT[s[left]]:
                    have -= 1
                left += 1
        left, right = res
        return s[left : right + 1] if resLen != float("inf") else ""

NeetCode.io

Reference: https://www.youtube.com/watch?v=jSto0O4AJbM