Minimum Window Substring
Problem Statement
Given two strings s
and t
, return the shortest substring of s
such that every character in t
, including duplicates, is present in the substring. If such a substring does not exist, return an empty string ""
.
You may assume that the correct output is always unique.
Example 1:
Input: s = "OUZODYXAZV", t = "XYZ"
Output: "YXAZ"
Explanation: "YXAZ"
is the shortest substring that includes "X"
, "Y"
, and "Z"
from string t
.
Example 2:
Input: s = "xyz", t = "xyz"
Output: "xyz"
Example 3:
Input: s = "x", t = "xy"
Output: ""
Constraints:
1 <= s.length <= 1000
1 <= t.length <= 1000
s
andt
consist of uppercase and lowercase English letters.
You should aim for a solution with O(n)
time and O(m)
space, where n
is the length of the string s
and m
is the number of unique characters in s
and t
.
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(m)
space, where n
is the length of the string s
and m
is the number of unique characters in s
and t
.
Hint 1
A brute force solution would involve checking every substring of s
against t
and returning the minimum length valid substring. This would be an O(n^2)
solution. Can you think of a better way? Maybe you should think in terms of frequency of characters.
Hint 2
We need to find substrings in s
that should have at least the characters of t
. We can use hash maps to maintain the frequencies of characters. It will be O(1)
for lookups. Can you think of an algorithm now?
Hint 3
We can use a dynamically sized sliding window approach on s
. We iterate through s
while maintaining a window. If the current window contains at least the frequency of characters from t
, we update the result and shrink the window until it is valid.
Hint 4
We should ensure that we maintain the result substring and only update it if we find a shorter valid substring. Additionally, we need to keep track of the result substring’s length so that we can return an empty string if no valid substring is found.
Solution
Brute Force
def min_window(s: str, t: str) -> str: if not t: return ""
count_t = {} for c in t: count_t[c] = 1 + count_t.get(c, 0)
result, result_len = [-1, -1], float("infinity") for i in range(len(s)): count_s = {} for j in range(i, len(s)): count_s[s[j]] = 1 + count_s.get(s[j], 0)
flag = True for c in count_t: if count_t[c] > count_s.get(c, 0): flag = False break
if flag and (j - i + 1) < result_len: result_len = j - i + 1 result = [i, j]
l, r = result return s[l : r + 1] if result_len != float("infinity") else ""
Time complexity: O(n^2)
Space complexity: O(m)
Sliding Window
def min_window(s: str, t: str) -> str: if not t: return ""
count_t, window = {}, {} for c in t: count_t[c] = 1 + count_t.get(c, 0)
have, need = 0, len(count_t) result, result_len = [-1, -1], float("infinity") left = 0 for right in range(len(s)): c = s[right] window[c] = 1 + window.get(c, 0)
if c in count_t and window[c] == count_t[c]: have += 1
while have == need: if (right - left + 1) < result_len: result = [left, right] result_len = right - left + 1
window[s[left]] -= 1 if s[left] in count_t and window[s[left]] < count_t[s[left]]: have -= 1 left += 1 l, r = result return s[l : r + 1] if result_len != float("infinity") else ""
Time complexity: O(n)
Space complexity: O(m)