712461. Minimum Window Substring
Minimum Window Substring
Slug: minimum-window-subsequence Difficulty: Medium Id: 712461 Topic Tags: Dynamic Programming, Arrays, Algorithms Company Tags: None
Summary
The Minimum Window Substring problem involves finding the shortest window in a given string that contains all characters of another input string. The goal is to find the smallest substring within the original string that has all the characters present in the target string.
Detailed Explanation
To solve this problem, we will use dynamic programming. We will create two pointers, start and end, to traverse the original string. The start pointer points to the beginning of the current window, while the end pointer points to the end of the current window.
We also maintain a dictionary, dict, to keep track of the frequency of each character in the target string. As we traverse the original string, we update the frequency of each character in the dict. When we find a character that is not present in the target string or if its frequency becomes zero, we move the start pointer forward until we find all characters from the target string again.
Here's the step-by-step breakdown:
- Initialize
startandendpointers to 0. - Create an empty dictionary
dict. - Iterate through the original string using the
endpointer. - For each character, update its frequency in the
dict. - If the frequency of a character becomes zero or if it is not present in the target string, move the
startpointer forward until we find all characters from the target string again. - Update the minimum window size and the start and end indices accordingly.
- Return the minimum window substring.
Here's an example:
Original String: "ADOBECODEBANC" Target String: "ABC"
Window: "BANC" is the smallest window that contains all characters of the target string.
Time complexity: O(n), where n is the length of the original string. Space complexity: O(1), as we only use a constant amount of space to store the dictionary and pointers.
Optimized Solutions
Java
public class MinimumWindowSubstring {
public static String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return "";
}
int start = 0;
int end = 0;
int formed = 0;
int windowStart = 0;
int minLength = Integer.MAX_VALUE;
String result = "";
int[] dict = new int[256];
for (int i = 0; i < t.length(); i++) {
dict[t.charAt(i)]++;
}
while (end < s.length()) {
char rightChar = s.charAt(end);
if (dict[rightChar] > 0) {
formed++;
}
dict[rightChar]--;
while (formed == t.length() && start <= end) {
char leftChar = s.charAt(start);
if (end - start + 1 < minLength) {
minLength = end - start + 1;
windowStart = start;
result = s.substring(windowStart, end + 1);
}
dict[leftChar]++;
if (dict[leftChar] > 0) {
formed--;
}
start++;
}
end++;
}
return result;
}
}