'''
keys: sliding window
Solutions:
Similar:
T: 
S: 
'''
from typing import List
from collections import Counter
import collections


class Solution:
    
    # educative.io version
    # https://www.educative.io/courses/grokking-the-coding-interview/xoyL4q6ApNE
    # T: O(N+M) where ‘N’ and ‘M’ are the number of characters 
    # in the input string and the pattern respectively.
    # S: O(M) for hashmap
    def minWindow2(self, s: str, t: str) -> str:
        res = ""
        p_ct = collections.Counter(t) # representing residue, i.e., to be matched
        
        matched = 0
        l = 0
        for r, c in enumerate(s):
            if c in p_ct:
                p_ct[c] -= 1 # p_ct[c] could be negative, we don change matched if negative 
                # we only care the char exists or not, do not care frequencybv
                if p_ct[c] >= 0: # every matching instance of a character.
                    matched += 1  

            while matched == len(t): # check len(t) since matching all chars in t
                tmp = s[l:r+1] # checking the substring
                if not res or len(tmp) < len(res): # a shorter res
                    res = tmp
                # shrinking the left pointer
                l_c = s[l]
                l += 1
                if l_c in p_ct:
                    '''
                    e.g., we might have two ‘a’ in the sliding window when we only
                    need one ‘a’. In that case, when we encounter the first ‘a’, 
                    we will simply shrink the window without decrementing the 
                    matched count. e.g., those negatives in p_ct[c]
                    '''
                    if p_ct[l_c] == 0: # could have redundant matching chars
                        matched -= 1 
                    p_ct[l_c] += 1

        return res
    
    
    # sliding window
    '''
    The solution is pretty intuitive. We keep expanding the window by moving
    the right pointer. When the window has all the desired characters, we 
    contract (if possible) and save the smallest window till now.
    O(|S| + |T|) for S and T
    '''
    def minWindow1(self, s: str, t: str) -> str:
        if not s or not t: return ""
        # Dictionary which keeps a count of all the unique characters in t.
        dict_t = Counter(t)
    
        # Number of unique characters in t, which need to be present in the 
        # desired window.
        required = len(dict_t)
    
        # left and right pointer
        l, r = 0, 0
    
        # formed is used to keep track of how many unique characters in t 
        # are present in the current window in its desired frequency.
        # e.g. if t is "AABC" then the window must have two A's, one B and
        # one C. Thus formed would be = 3 when all these conditions are met.
        formed = 0
    
        # Dictionary which keeps a count of all the unique characters in 
        # the current window.
        window_counts = {}
    
        # ans tuple of the form (window length, left, right)
        ans = float("inf"), None, None
    
        while r < len(s):
    
            # Add one character from the right to the window
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1
    
            # If the frequency of the current character added equals to the 
            # desired count in t then increment the formed count by 1.
            if character in dict_t and window_counts[character] ==\
                dict_t[character]:
                formed += 1
    
            # Try and contract the window till the point where it ceases to 
            # be 'desirable'.
            while formed == required: # we don't need "l <= r and "
                # Save the smallest window until now.
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)
                    
                character = s[l]
    
                # The character at the position pointed by the `left` pointer 
                # is no longer a part of the window.
                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < \
                    dict_t[character]:
                    formed -= 1
    
                # Move the left pointer ahead, this would help to look for a
                # new/shorter window.
                l += 1    
    
            # Keep expanding the window once we are done contracting.
            r += 1    
        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]
        
sol = Solution()
print (sol.minWindow1("aaaaaaaaaaaabbbbbcdd", "abcdd")) 
    
# TLE
def minWindow(self, s: str, t: str) -> str:
    if not s or not t: return ""
    lt = len(t)
    for len_ in range(lt, len(s) + 1):
        for idx in range(len(s) - len_ + 1):
            tmp = s[idx: idx + len_]
            if self.helper(t, tmp):
                return tmp
    return ""
            
def helper(self, target, source):
    t_ct = Counter(target)
    s_ct = Counter(source)
    for c, ct in t_ct.items():
        if c not in s_ct or ct > s_ct[c]:
            return False
    return True
    
