minimum window substring

minimum_window_substring.py

"""
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 "".


A substring is a contiguous sequence of characters within the string.

This is fucking hard.
"""


from collections import Counter


# This solution will work for base test cases but not for exhaustive cases:
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "": return ""
        
        left = 0
        test_str_ctr = {}
        p_ctr = {} 
        p_ctr.update(Counter(t))
        ctr_items = sum(p_ctr.values())
        min_len = float("inf")
        min_str = (0, 0)
        total_ct = 0
        print("before, total_ct, left, right, char, test_str_ctr, p_ctr")
        for right, char in enumerate(s):
            if char in p_ctr:
                test_str_ctr[char] = test_str_ctr.get(char, 0) + 1
                if test_str_ctr[char] == p_ctr[char]:
                    total_ct += 1  # this is not needed! understand the concept. this is a hack.
            
            
            # print("before", total_ct, left, right, char, test_str_ctr, p_ctr)
            while total_ct == ctr_items:
                if min_len > right - left + 1:
                    min_str = (left, right+1)
                    min_len = right - left + 1
                
                char = s[left]
                if char in p_ctr:
                    test_str_ctr[char] -= 1
                    if test_str_ctr[char] < p_ctr[char]:
                        total_ct -= 1
                left += 1
            # print("after", total_ct, left, right, char, test_str_ctr, p_ctr)

        res = ""
        for c_idx in range(*min_str):
            res += s[c_idx]
        return res


# This resolves the issue. Conceptually, 
# you need to compare that all frequencies of each character are >= in target string
from collections import Counter
from functools import partial


class Solution:
    
    @staticmethod
    def minimumDictValCount(src_dict: dict, target_dict: dict):
            return all(src_dict.get(k, 0) >= v for k,v in target_dict.items())
    
    def minWindow(self, s: str, t: str) -> str:
        if t == "": return ""
        left = 0
        target_len = len(t)
        test_str_ctr = {}
        p_ctr = {} 
        p_ctr.update(Counter(t))
        min_len = float("inf")
        min_str = (0, 0)
        total_ct = 0
        hasMinSumOfWindow = partial(self.minimumDictValCount, test_str_ctr, p_ctr)
        
        for right, char in enumerate(s):
            if char in p_ctr:
                test_str_ctr[char] = test_str_ctr.get(char, 0) + 1
            
            
            while (
                test_str_ctr == p_ctr or hasMinSumOfWindow()):
                if min_len > right - left + 1:
                    min_str = (left, right+1)
                    min_len = right - left + 1
                char = s[left]
                if char in p_ctr:
                    test_str_ctr[char] -= 1
                left += 1

        res = ""
        for c_idx in range(*min_str):
            res += s[c_idx]
        return res