Minimum Window Substring

Sources: leetcode 76

Rating: hard

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

  • Solve without using a sort library.
  • Sort in single-pass algorithm using constant space.
def minWindow(s: str, t: str) -> str:
    # return the minimum window in s which contains all characters in t

Solution

First handle, the edge case of s being too short to contain t. Next use a dictionary d to figure out the counts of the letters in t, and a counter missing to determine how many letters must be included.

def minWindow(s, t):
    if len(s) < len(t):
        return ''
    d = {}
    for c in t:
        if c not in d:
            d[c] = 0
        d[c] += 1
    missing = len(t)
    # return the minimum window in s which contains all characters in t

Next, set up index trackers l and r to manage the sliding window, with L and R as the final result to be used, updated as missing letters are found.

def minWindow(s, t):
    if len(s) < len(t):
        return ''
    d = {}
    for c in t:
        if c not in d:
            d[c] = 0
        d[c] += 1
    missing = len(t)
    l = L = R = 0
    for r, c in enumerate(s, 1):    
        if c in d and d[c] > 0:
            missing -= 1
        if c in d:
            d[c] -= 1
        while l < r and not missing:
            if not R or r - l < R - L:
                L, R = l, r
            if s[l] not in d:
                l += 1
            else:
                d[s[l]] += 1
                if d[s[l]] > 0:
                    missing += 1
                l += 1
    # return the minimum window in s which contains all characters in t

Once the L and R limits are known, the substring is simply the subset of s.

Final Code

def minWindow(s, t):
    if len(s) < len(t):
        return ''
    d = {}
    for c in t:
        if c not in d:
            d[c] = 0
        d[c] += 1
    missing = len(t)
    l = L = R = 0
    for r, c in enumerate(s, 1):    
        if c in d and d[c] > 0:
            missing -= 1
        if c in d:
            d[c] -= 1
        while l < r and not missing:
            if not R or r - l < R - L:
                L, R = l, r
            if s[l] not in d:
                l += 1
            else:
                d[s[l]] += 1
                if d[s[l]] > 0:
                    missing += 1
                l += 1
    return s[L:R]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s