76. Minimum Window Substring

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.

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

 

'''
[1] brute force)

idea::
Find sub_string from s and check if it contains all the characters of t using nested loop and hashmap.

-T/C: O(n*2 + n*m)
-S/C: O(m+n)
'''

'''
[2] sliding window - need to optimization,,,,)

idea::
1. store all frequencies of the characters of t in hashmap.
2. while sliding window, check if it contains all the characters of t.
3. when moving window, fast pointer move until the window contains all of t. after that, if the window contains all, 
slow pointer move forward.

code::
(below)

-T/C: O(58*(m+n))
-S/C: O(58*2)
'''

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s)<len(t):
            return ""

        tmap=[0 for _ in range(58)] # ascii code 'A'~'z'
        for c in t:
            tmap[ord(c)-ord('A')]+=1

        smap=[0 for _ in range(58)] 

        slow=0
        fast=0
        while fast<len(t):
            smap[ord(s[fast])-ord('A')]+=1
            fast+=1

        min_start=-1
        min_size=float(math.inf)
        while fast<=len(s):
            if self.hasT(smap,tmap):
                if min_size > fast-slow:
                    min_size=fast-slow
                    min_start=slow
                smap[ord(s[slow])-ord('A')]-=1
                slow+=1

            elif fast<len(s):
                smap[ord(s[fast])-ord('A')]+=1
                fast+=1

            else:
                break
        if min_start==-1:
            return ""
        return s[min_start:min_start+min_size]
            
        
    def hasT(self,smap,tmap):
        for s,t in zip(smap,tmap):
            if s<t:
                return False
        return True