How to Solve Minimum Window Substring
Minimum Window Substring Introduction
Minimum Window Substring Introduction
The Minimum Window Substring problem starts by providing us with two strings, s and t. The goal is to find the smallest window from the string s, that contains all the characters from a t. This problem requires careful consideration and checks to keep track of the frequency of characters that appear and storing them in the appropriate data structure as well as using a sliding window with two pointers to search for the minimum substring by continuously expanding or shifting the window and keeping track of the smallest window found so far.
Minimum Window Substring Problem
Minimum Window Substring 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.
Example Inputs and Outputs
Example 1
Input: s1 = "ADOBECODEBANC" , t1 = "ABC"
Output: "BANC"
Example 2
Input: s2 = "ab" , t2 = "b"
Output: "b"
Example 3
Input: s3 = "a" , t3 = "aa"
Output: ""
Minimum Window Substring Solutions
Minimum Window Substring Solutions
To solve this problem, we can use a sliding window approach along with two pointers to find the minimum window substring in the given string. The goal is to find the smallest window in the string that contains all the characters from a specified pattern string.
In this solution, we start by counting the frequencies of characters in the pattern string and storing them in a dictionary. Then, we initialize two pointers, 'left' and 'right', to the beginning of the string. We iterate through the string using the 'right' pointer and keep track of the characters and their frequencies in the current window.
Whenever we find a character that matches one of the required characters and its frequency matches the required frequency, we increment a counter variable. If all the required characters are found in the current window, we try to minimize the window by moving the 'left' pointer until the window is no longer valid. During this, we update the minimum window substring if we find a smaller window.
We repeat the process of moving the pointers and checking the validity of the window until we reach the end of the string. Finally, we return the minimum window substring found during the iteration.
from collections import defaultdict
def minWindow(s, t):
# Create a dictionary to keep track of character frequencies in t
target = defaultdict(int)
# Count the frequencies of characters in t and store in the dictionary
for char in t:
target[char] += 1
# Initialize variables for left and right pointers, and the minimum window substring
left = 0
right = 0
min_len = float('inf')
min_window = ''
# Variable to keep track of the number of characters in t that are still needed to form a valid window
required = len(target)
# Variable to keep track of the number of characters in the current window that match the required characters
formed = 0
# Create a dictionary to store the frequencies of characters in the current window
window_counts = defaultdict(int)
# Loop through the string s using the right pointer
while right < len(s):
# Add the current character to the window_counts dictionary and increment its frequency
char = s[right]
window_counts[char] += 1
# Check if the current character is one of the required characters and if its frequency matches the required frequency
if char in target and window_counts[char] == target[char]:
formed += 1
# Try to minimize the window by moving the left pointer if all required characters are found in the current window
while left <= right and formed == required:
# Update the minimum window substring if a smaller window is found
if right - left + 1 < min_len:
min_len = right - left + 1
min_window = s[left:right+1]
# Remove the leftmost character from the window and update its frequency
char = s[left]
window_counts[char] -= 1
# Check if the removal of the leftmost character affects the validity of the window
if char in target and window_counts[char] < target[char]:
formed -= 1
# Move the left pointer to the right to shrink the window
left += 1
# Move the right pointer to the right to expand the window
right += 1
# Return the minimum window substring
return min_window
# Test cases
s1 = "ADOBECODEBANC"
t1 = "ABC"
print(minWindow(s1, t1)) # Output: "BANC"
s2 = "a"
t2 = "a"
print(minWindow(s2, t2)) # Output: "a"
s3 = "a"
t3 = "aa"
print(minWindow(s3, t3)) # Output: ""
s4 = "ab"
t4 = "b"
print(minWindow(s4, t4)) # Output: "b"1from collections import defaultdict
2
3def minWindow(s, t):
4 # Create a dictionary to keep track of character frequencies in t
5 target = defaultdict(int)
6
7 # Count the frequencies of characters in t and store in the dictionary
8 for char in t:
9 target[char] += 1
10
11 # Initialize variables for left and right pointers, and the minimum window substring
12 left = 0
13 right = 0
14 min_len = float('inf')
15 min_window = ''
16
17 # Variable to keep track of the number of characters in t that are still needed to form a valid window
18 required = len(target)
19
20 # Variable to keep track of the number of characters in the current window that match the required characters
21 formed = 0
22
23 # Create a dictionary to store the frequencies of characters in the current window
24 window_counts = defaultdict(int)
25
26 # Loop through the string s using the right pointer
27 while right < len(s):
28 # Add the current character to the window_counts dictionary and increment its frequency
29 char = s[right]
30 window_counts[char] += 1
31
32 # Check if the current character is one of the required characters and if its frequency matches the required frequency
33 if char in target and window_counts[char] == target[char]:
34 formed += 1
35
36 # Try to minimize the window by moving the left pointer if all required characters are found in the current window
37 while left <= right and formed == required:
38 # Update the minimum window substring if a smaller window is found
39 if right - left + 1 < min_len:
40 min_len = right - left + 1
41 min_window = s[left:right+1]
42
43 # Remove the leftmost character from the window and update its frequency
44 char = s[left]
45 window_counts[char] -= 1
46
47 # Check if the removal of the leftmost character affects the validity of the window
48 if char in target and window_counts[char] < target[char]:
49 formed -= 1
50
51 # Move the left pointer to the right to shrink the window
52 left += 1
53
54 # Move the right pointer to the right to expand the window
55 right += 1
56
57 # Return the minimum window substring
58 return min_window
59
60
61# Test cases
62s1 = "ADOBECODEBANC"
63t1 = "ABC"
64print(minWindow(s1, t1)) # Output: "BANC"
65
66s2 = "a"
67t2 = "a"
68print(minWindow(s2, t2)) # Output: "a"
69
70s3 = "a"
71t3 = "aa"
72print(minWindow(s3, t3)) # Output: ""
73
74s4 = "ab"
75t4 = "b"
76print(minWindow(s4, t4)) # Output: "b"Time/Space Complexity Analysis
- Time Complexity: O(N), where N is the length of the input string s, as we iterate through s once.
- Space Complexity: O(M), where m is the length of the input string t, to store the frequency of characters in the target string.
Achieving O(1) Space:
It's important to note we could achieve O(1) space by creating a hash array of size 256 (assuming ASCII characters) to store the frequency of each character in the pattern string. This would be independant of input size and keep it constant. But for simplicity we will keep it to O(m) as this fits requirements.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
