Minimum Window Substring - Python Solution

 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        dict_t = Counter(t)
        required = len(dict_t)
        filtered_s = []
        for i,char in enumerate(s):
            if char in dict_t:
                filtered_s.append((i,char))
        l,r = 0,0
        formed = 0
        window_counts = {}
        ans = float("inf"),None,None
        while r < len(filtered_s):
            character = filtered_s[r][1]
            window_counts[character] = window_counts.get(character,0)+1
            if window_counts[character] == dict_t[character]:
                formed+=1
                
            while l<=r and formed == required:
                character = filtered_s[l][1]
                
                end = filtered_s[r][0]
                start = filtered_s[l][0]
                if end-start+1 < ans[0]:
                    ans = (end-start+1,start,end)
                
                window_counts[character] -=1
                if window_counts[character] < dict_t[character]:
                    formed-=1
                l +=1
            r+=1
        return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

TC: O(∣S∣+∣T∣) SC:O(∣S∣+∣T∣)