Minimum Window Substring

Minimum Window Substring

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 “”.

Example

Input: s = “ADOBECODEBANC”, t = “ABC”

Output: “BANC”

Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Approach 1:

I believe having a sliding window approach will work given the hint from the title.

I plan to have two hashmap that stores the characters and frequencies of two strings.

I will iterate through string s to check and see if a substring of s matches the key and values of hashmap created by Counter(t).

I will efficiently compare all the substrings by having a tuple that keeps the length and the indices of the substring.

Implementation:

from collections import Counter
class Solution:


    def minWindow(self, s: str, t: str) -> str:
        left = right = matched = 0
        dict_t = Counter(t)
        required = len(dict_t)
        ans = len(s) + 1, None, None
        window = {}
        while right < len(s):
            char = s[right]
            window[char] = window.get(char, 0) + 1
            if char in dict_t dict_t[char] == window[char]:
                matched += 1
            if matched == required and left <= right:
                charL = s[left]
                if right - left + 1 < ans[0]:
                    ans = (right - left + 1, left, right)
                window[charL] -= 1
                if charL in dict_t and window[charL] < dict_t[charL]:
                    matched -= 1
                left += 1
            right += 1
        
        return s[ans[1]:ans[2] + 1] if ans[0] < len(s) + 1 else ""
        
        

Complexity Analysis:

Time Complexity: O(2S + T)

Space Complexity: O(S + T)

Reflection

My first hard question, it was hard to understand at first, but got it!