class Solution:

     def minWindow(self, s: str, t: str) -> str:

         n = len(s)

         if n==0:

             return ""

         if len(t)==0:

             return s

         #if s == t:

         #    return s

         dic = {}

         dic2= {}

         for i in range(len(t)):

             dic.update({t[i]:0})

             if t[i] in dic2.keys():

                 dic2.update({t[i]:dic2[t[i]]+1})

             else:

                 dic2.update({t[i]:1})

         #dicount = len(t)

         i = 0

         j = 0

         minstr = ""

         minwidth = n

         while i <=j and j<n :

             #j++

             if s[j] in t:

                 dic.update({s[j]:dic[s[j]]+1})

                 valid = True

                 for k in dic.keys():

                     if dic[k]<dic2[k]:

                         valid = False

                         break

                 if valid:

                     #valid

                     curlen = j-i+1

                     if curlen<=minwidth:

                         minwidth = curlen

                         minstr = s[i:j+1]

                     #i++

                     while i<=j:

                         if s[i] not in dic.keys():

                             i += 1

                         else:

                             if dic[s[i]]>dic2[s[i]]:

                                 dic.update({s[i]:dic[s[i]]-1})

                                 i += 1

                             else:

                                 curlen = j-i+1

                                 if curlen <= minwidth:

                                     minwidth = curlen

                                     minstr = s[i:j+1]

                                 break

                 #else:

                     #invalid

             j += 1

         return minstr