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: ""

Expand the window until have=need, then shrink the window till have<need.

• Create a frequency map tmap for characters in t
• Set need = len(tmap) (unique characters required)
• Loop through s with r
  • Add s[r] to window.
  • If s[r] matches the required frequency in tmap, increment have.
  • While have == need
    • Update res if the current window is smaller.
    • Remove s[l] from window
    • If s[l] is in tmap and its count drops below the required frequency, decrement have.
    • Increment left.
• Return substring s[l:r+1] if valid window found, else return empty string.

In [1]:

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
            #Remove s[l] from window  
            window[s[l]]-=1
            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 [2]:

minWindow("OUZODYXAZV","OOY")

Out[2]:

'OUZODY'

In [3]:

minWindow("x","xy")

Out[3]:

''

In [4]:

float("infinity")

Out[4]:

inf

In [5]:

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

Out[5]:

2