76. Minimum Window Substring

Problem Description

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

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

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

My Idea

The idea here is to utilize the Sliding Window technique and hashmaps for the char frequencies of the windows. We expand the window to the right until we get a match. Once we have a match, we contract the window from the left until no longer have a match. Then we continue expanding on the right and repeat until the end of s.

My solution

# Time Complexity: O(n)
def minWindow(s: str, t: str) -> str:
    if t == "":
        return ""
    l = 0
    d1 = dict()
    d2 = dict()
    res = ""
    resL = float("inf")
    for c in t:
        d1[c]=1+d1.get(c,0)
    present = 0
    needed = len(d1)
    for r in range(len(s)):
        d2[s[r]]=1+d2.get(s[r],0)

        if s[r] in d1 and d1[s[r]]==d2[s[r]]:
            present+=1
        while present == needed:
            if (r-l+1) < resL:
                res = s[l:r+1]
                resL = len(res)

            d2[s[l]]-=1
            if s[l] in d1 and d2[s[l]]<d1[s[l]]:
                present-=1
            l+=1
    return res

76. Minimum Window Substring - LeetCode