class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        #left, right pointers 
        # use dictionary as hash
        #positive and negative values represent in excess or in debt 
        l=len(s)
        min_len=float('inf')
        m_start=0
        hash_dict=collections.defaultdict(int)
        count=len(t) #count the number of char in t still unidentified in s 
        for ch in t: 
            hash_dict[ch]+=1
        left,right=0,0
        while right<l:
            if s[right] in hash_dict:
                #when meet a key char, record in hash,(negative value represent in excess) 
                #if it is one of what we are currently looking for(hash value>0), reduce count 
                if hash_dict[s[right]]>0:count-=1
                hash_dict[s[right]]-=1
            right+=1
            while count==0: 
                if min_len>right-left+1:#record the shorter solution if encounter one 
                    m_start=left
                    min_len=right-left+1
                if s[left] in hash_dict: 
                    #when we are to leave out one key char, register in hash
                    #only start looking for it on the right when hash value is positive 
                    hash_dict[s[left]]+=1
                    if hash_dict[s[left]]>0:count+=1 
                left+=1 
        if min_len==float('inf'): return ''
        return s[m_start:m_start+min_len-1]