76. Minimum Window Substring — LeetCode(Python)

I got you!

Problem:

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 two hash maps, t_dict for keeping count of the frequency of each element in t, and window for keeping count of the frequency of each element in the substring of s that we are considering.

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 resLen and res, where we store the length of the minimum window and the indices bounding that window respectively.

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 —

Also, the minimum window could be the entire string s, and t could possibly have all unique characters.

Thus, if S is the length of string s and T is the length of string t,

Time Complexity: O(S + T)

Space Complexity: O(S + T)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

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