76. Minimum Window Substring — LeetCode(Python)

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

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
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.
  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s and t consist of uppercase and lowercase English letters.

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.

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.

I don’t have friends:

Let’s be friends!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store