0018 - Minimum Window Substring - Revise

Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

Example 1:

Input: s = "OUZODYXAZV", t = "XYZ"

Output: "YXAZ" Explanation: "YXAZ" is the shortest substring that includes "X", "Y", and "Z" from string t.

Example 2:

Input: s = "xyz", t = "xyz"

Output: "xyz" Example 3:

Input: s = "x", t = "xy"

Output: ""

• Create tmap for t

  • Store character counts of t.

• Set need = len(tmap)

  • Total unique characters required.

• Loop through s with r (right pointer)

  • Add s[r] to window.
  • If s[r] matches count in tmap, increment have.

• While have == need

  • Update res if window size is smaller.
  • Pop s[l] from window.
  • If s[l] in tmap and window count drops below tmap, reduce have.
  • Move l right.

• Return s[l:r+1] if valid window found, else return "".

In [12]:

def minWindow(s,t):
    if t=="":
        return ""
    tmap,window={},{}
    #Build tmap
    for c in t:
        tmap[c] = 1 + tmap.get(c,0)
    have, need=0, len(tmap)
    res, resLen = [-1,-1], float("infinity")
    l=0
    for r in range(len(s)):
        c=s[r]
        window[c] = 1 + window.get(c,0) #add to window
        if c in tmap and window[c] == tmap[c]:
            have+=1
        while have==need:
            if (r-l+1)<resLen:
                res=[l,r]
                resLen=r-l+1
            #pop from left
            window[s[l]]-=1
            #update have if needed
            if s[l] in tmap and window[s[l]]<tmap[s[l]]:
                have-=1
            l+=1
    l,r=res
    if resLen != float("infinity"):
        return s[l : r + 1]
    else:
        return ""

In [13]:

minWindow("OUZODYXAZV","OOY")

Out[13]:

'OUZODY'

In [14]:

minWindow("x","xy")

Out[14]:

''

In [15]:

float("infinity")

Out[15]:

inf

In [16]:

len({'X':2,'Y':1})

Out[16]:

2

In [ ]: