Problem Description
Given two strings s
and t
, return the minimum window in s
which will contain all the characters in t
. If there is no such window in s
that covers all characters in t
, return the empty string ""
.
Note that if there is such a window, it is guaranteed that there will always be only one unique minimum window in s
.
Link to the problem: https://leetcode.com/problems/minimum-window-substring/
Solution
To solve this problem, we can use the sliding window technique. We will define two pointers, left
and right
, which will point to the start and end of the window, respectively. We will move the right
pointer until we have a window that contains all the characters in t
. After that, we will move the left
pointer to the right until we cannot move it any further without losing the window property. We will keep track of the minimum window we have seen so far and continue to move the pointers until we have gone through the entire string.
class Solution:
def minWindow(self, s: str, t: str) -> str:
# Initialize two hash maps
freq_t = {}
freq_window = {}
# Count the frequency of each character in t
for char in t:
freq_t[char] = freq_t.get(char, 0) + 1
# Initialize the window and other variables
left, right = 0, 0
count = 0
min_window = ""
# Move the right pointer until we have a window that contains all the characters in t
while right < len(s):
# Increment the frequency of the character at the right pointer
freq_window[s[right]] = freq_window.get(s[right], 0) + 1
# If the frequency of the character at the right pointer is less than or equal to the frequency of that character in t, then we have found a valid character
if s[right] in freq_t and freq_window[s[right]] <= freq_t[s[right]]:
count += 1
# Move the left pointer until we cannot move it any further without losing the window property
while left <= right and count == len(t):
# Update the minimum window
if not min_window or len(s[left:right+1]) < len(min_window):
min_window = s[left:right+1]
# Decrement the frequency of the character at the left pointer
freq_window[s[left]] -= 1
# If the frequency of the character at the left pointer becomes less than the frequency of that character in t, then we have lost a valid character
if s[left] in freq_t and freq_window[s[left]] < freq_t[s[left]]:
count -= 1
# Move the left pointer to the right
left += 1
# Move the right pointer to the right
right += 1
return min_window
Complexity Analysis
The time complexity of this solution is O(n), where n is the length of the string s
. We only iterate through the string once, and each iteration involves moving the left and right pointers at most n times in total.
The space complexity of this solution is O(m), where m is the length of the string t
. We use two hash maps to count the frequency of each character in t
, which takes up O(m) space.
Conclusion
In this blog post, we saw how to solve the Minimum Window Substring problem using the sliding window technique. This problem can be tricky, but by breaking it down into smaller steps and using the sliding window technique, we were able to come up with an efficient solution. Happy Coding!😎