0076 Minimum Window Substring

0076 Minimum Window Substring#

Problem#

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Examples#

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints#

m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.

Followup#

Could you find an algorithm that runs in O(m + n) time?

Analysis#

Solution#

def minWindow(s, t):
    # initialize some hash map
    map_t = {c:t.count(c) for c in set(t)}
    map_s = {}

    # two pointer for sliding window
    left, right = 0, 0
    # record minimum string start index and length
    start, min_length = 0, len(s) + 1

    # define a helper function
    def isValidSubset(map_t, map_s):
        # check if map_t is a valid subset of map_s
        for key in map_t.keys():
            if key not in map_s or map_s[key] < map_t[key]:
                return False
        return True

    # main algorithm
    while right < len(s):
        # character at right pointer
        c = s[right]
        # enlarge window
        right += 1
        # save to map
        if c in map_s:
            map_s[c] += 1
        else:
            map_s[c] = 1

        # shrink window if current window has all the target characters
        # keys of target are in s, and occurences in target should be less than that in the source map 
        while isValidSubset(map_t, map_s):
            # update substring length
            # note the right pointers has moved forward by 1 step
            length = right - left
            if length < min_length:
                min_length = length
                start = left 

            # remove left char
            c = s[left]
            # shrink window
            left += 1
            # remove occurence in map_s
            map_s[c] -= 1
            if map_s[c] == 0:
                map_s.pop(c)

    # return
    return s[start:start+min_length] if min_length <= len(s) else ""

# test
s = "ADOBECODEBANC" 
t = "ABC"
print(minWindow(s, t))

s = "a" 
t = "a"
print(minWindow(s, t))

s = "a" 
t = "aa"
print(minWindow(s, t))

BANC
a
Contents