# 76. Minimum Window Substring — LeetCode(Python)

--

I got you!

# 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.

**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.

**Follow up:** Could you find an algorithm that runs in `O(m + n)`

time?

# Solution:

`if t == '': return ''`

t_dict, window = {}, {}

for c in t:

t_dict[c] = 1 + t_dict.get(c, 0)

have, need = 0, len(t_dict)

res, resLen = [-1, -1], float('inf')

l = 0

for r in range(len(s)):

c = s[r]

window[c] = 1 + window.get(c, 0)

if c in t_dict and window[c] == t_dict[c]:

have += 1

while have == need:

# update our result

if r - l + 1 < resLen:

resLen = r - l + 1

res = [l, r]

# pop from left of window

window[s[l]] -= 1

if s[l] in t_dict and window[s[l]] < t_dict[s[l]]:

have -= 1

l += 1

l, r = res

return s[l:r+1]

# Explanation —

We use a sliding window approach here.

We use two hash maps, ** t_dict** for keeping count of the frequency of each element in

**, and**

*t***for keeping count of the frequency of each element in the substring of**

*window***that we are considering.**

*s*If the frequency of an element in a given window is greater than or equal to the frequency of that element in t, we increment the number of matches we have.

When we encounter a new element in ** s**, we update it’s frequency in the map

*window.*If this new character is present in ** t,** and the frequency of the character in both dictionaries is the same for the first time, we increment the value of

*have.*When the number of matches we have is equal to the number of unique characters in t, we have found a substring.

So, when ** have == need,** we update the value of

**and**

*resLen***where we store the length of the minimum window and the indices bounding that window respectively.**

*res,*Next, we shrink the window from the left. The count of that element in the window is decremented. Any changes made to the number of matches are updated, and the left end of the window is slid.

Finally, we return the substring in ** s** between the indices stored in

*res.*## Time and Space Complexity —

In the worst case, we might end up traversing through each element in the string ** s **twice, by both the pointers.

Also, the minimum window could be the entire string ** s,** and

**could possibly have all unique characters.**

*t*Thus, if ** S** is the length of string

**and**

*s**T*is the length of string

*t,*Time Complexity: O(S + T)

Space Complexity: O(S + T)