76. Minimum Window Substring

• categories: Code, Interview Question, leetcode, Hard
• source: https://leetcode.com/problems/minimum-window-substring
• topics: String Manipulation, Sliding Window

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.

Idea

Sliding window for filtered characters, update when all char numbers are at least equal to frequency of the initial string

Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s or len(t) > len(s):
            return ""
        
        count_t = Counter(t)
        
        # Pre-check for validity of `t` in `s`
        if not count_t.keys() <= set(s):
            return ""
        
        # Filter relevant characters from `s`
        filtered_s = [(c, i) for i, c in enumerate(s) if c in count_t]
        
        len_filtered = len(filtered_s)
        len_t = len(count_t)
        if len_filtered < len(t):
            return ""
        
        chars_ok = 0
        count_s = Counter()
        start = 0
        i = 0
        min_len = float(inf)
        ans = (0, -1)
 
        while i < len_filtered:
            c = filtered_s[i][0]
            count_s[c] += 1
            
            # Check if current character satisfies `t` requirements
            if count_s[c] == count_t[c]:
                chars_ok += 1
            
            # If all characters are satisfied
            while chars_ok == len_t:
                start_char = filtered_s[start][0]
                
                # Update minimum window
                start_idx, end_idx = filtered_s[start][1], filtered_s[i][1]
                if end_idx - start_idx < min_len:
                    ans = (start_idx, end_idx)
                    min_len = end_idx - start_idx
                
                # Shrink the window
                count_s[start_char] -= 1
                if count_s[start_char] < count_t[start_char]:
                    chars_ok -= 1
                start += 1
 
            i += 1
        
        return s[ans[0]:ans[1] + 1] if min_len != float(inf) else ""