Solution For Minimum Window Substring
The Minimum Window Substring problem is a famous problem on LeetCode that requires you to find the smallest window in a string that contains all the characters of another string. This problem can be solved using a sliding window technique and hashing.
Here is a detailed solution on how to solve the Minimum Window Substring problem on LeetCode:
Step 1: Initialize two hash tables
- One hash table will store the frequency of each character in target string.
- The other hash table will store the frequency of each character in the sliding window.
Step 2: Determine the length of the target string.
- This step is important as we will use it later to check if we have found the minimum substring.
Step 3: Traverse the string.
- For each character, update the frequency of that character in the sliding window hash table.
- Check if the current sliding window contains all the characters of the target string.
- If yes, move the start index of the sliding window until we have the minimum window that contains all the characters of the target string.
- If no, continue to slide the window and update the frequency of characters until we find a window that contains all the characters.
Step 4: Return the minimum window.
- If a minimum window is found, return it. Otherwise, return an empty string.
Here is the Python implementation of the above algorithm:
“`
def minWindow(s, t):
target = {}
window = {}
for ch in t:
target[ch] = target.get(ch, 0) + 1
left, correct, right, result = 0, 0, 0, ""
while right<len(s):
ch = s[right]
if ch in target:
window[ch] = window.get(ch, 0) + 1
if window[ch] == target[ch]:
correct += 1
while correct == len(target):
if not result or right-left+1<len(result):
result = s[left:right+1]
ch = s[left]
if ch in target:
window[ch] -= 1
if window[ch] < target[ch]:
correct -= 1
left += 1
right += 1
return result
“`
In the above implementation, we first initialize two hash tables for target and window and then calculate the length of target. We then traverse the string and update the frequency of characters in the window hash table and check if we have found all the characters of the target string. If we have found all characters, we move the start index of the window until we have found the minimum window. Finally, we return the minimum window that contains all the characters of the target string.
Step by Step Implementation For Minimum Window Substring
public class Solution { public String minWindow(String s, String t) { if(s == null || s.length() == 0 || t == null || t.length() == 0) return ""; //create a map to save the characters in t Mapmap = new HashMap<>(); for(int i = 0; i < t.length(); i++){ char c = t.charAt(i); if(map.containsKey(c)){ map.put(c, map.get(c)+1); }else{ map.put(c, 1); } } //maintain a counter to check whether match all characters in t int count = 0; //two pointers: begin-end, one point to tail and one head int begin = 0, end = 0; //distance between begin and end int min = Integer.MAX_VALUE; //head pointer of the result substring int head = 0; //loop through s while(end < s.length()){ //get a character char c = s.charAt(end); //if the map contains the character c, we consider it as a effective character if(map.containsKey(c)){ //then increment the count by 1 map.put(c, map.get(c)-1); //because the character c exists in t, we have to consider it as a valid character if(map.get(c) >= 0) //increment the count by 1 count ++; } end++; //when the count is equal to t's length, in other word, find a valid substring while(count == t.length()){ //if find a substring whose length is less than min, then update min if(end-begin < min) min = end - (head=begin); //if the map contains the character s[begin], we should plus one to make it invalid/not effective again char tempc = s.charAt(begin); if(map.containsKey(tempc)){ map.put(tempc, map.get(tempc) + 1); //plus one make it invalid if(map.get(tempc) > 0) //decrement the count by 1 count--; } //move the begin pointer to find the new substring begin ++ ; } } //return the result substring if(min == Integer.MAX_VALUE) return ""; return s.substring(head, head+min); } }
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC" Note: If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
/** * @param {string} s * @param {string} t * @return {string} */ // this is a sliding window problem var minWindow = function(s, t) { let map = {}; let count = t.length; let min = Infinity; let minStart = 0; // fill up the map with the counts of each character in t for (let i = 0; i < t.length; i++) { let c = t.charAt(i); map[c] = map[c] + 1 || 1; } // two pointers, left and right // as we move right, we decrement the count for each character we see in t // as soon as the count is 0, we know we have found all the characters in t // we then move left until the count is no longer 0 // we keep track of the minimum length window let left = 0; for (let right = 0; right < s.length; right++) { let c = s.charAt(right); if (map[c] > 0) { count--; } map[c]--; while (count === 0) { if (right - left + 1 < min) { min = right - left + 1; minStart = left; } let d = s.charAt(left); map[d]++; if (map[d] > 0) { count++; } left++; } } return min === Infinity ? "" : s.substring(minStart, minStart + min); };
class Solution { public: string minWindow(string s, string t) { // Base case if (t.size() > s.size()) return ""; // Initialize a map to keep track of all the unique characters in t unordered_maptarget; for (char c : t) target[c]++; // Initialize a map to keep track of the unique characters we've seen so far unordered_map seen; // Initialize two pointers, left and right int left = 0, right = 0; // Initialize a variable to keep track of the number of unique characters we've seen so far int unique = 0; // Initialize a variable to keep track of the length of the smallest window int minLen = INT_MAX; // Initialize a variable to keep track of the starting index of the smallest window int start = 0; // Loop through the string while (right < s.size()) { // If the character at the current index is not in the map, skip it if (target.find(s[right]) == target.end()) { right++; continue; } // If the character at the current index is in the map, increment the value at that key seen[s[right]]++; // If the character at the current index is in the map and we haven't seen it before, increment the unique counter if (seen[s[right]] == target[s[right]]) unique++; // If we've seen all the unique characters, move the left pointer while (unique == target.size()) { // If the current window is smaller than the smallest window we've seen so far, update the minimum length and starting index if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; } // If the character at the left pointer is not in the map, move the left pointer and continue if (target.find(s[left]) == target.end()) { left++; continue; } // If the character at the left pointer is in the map, decrement the value at that key seen[s[left]]--; // If the character at the left pointer is in the map and we've seen it before, decrement the unique counter if (seen[s[left]] < target[s[left]]) unique--; // Move the left pointer left++; } // Move the right pointer right++; } // Return the smallest window return minLen == INT_MAX ? "" : s.substr(start, minLen); } };
public class Solution { public string MinWindow(string s, string t) { // edge case: s is shorter than t if (s.Length < t.Length) { return ""; } // initialize a hashmap to store the characters in t and their counts var map = new Dictionary(); foreach (char c in t) { if (!map.ContainsKey(c)) { map[c] = 0; } map[c]++; } // initialize variables to keep track of the minimum window int minWindowStart = 0; int minWindowEnd = 0; int minWindowLength = int.MaxValue; // initialize variables to keep track of the number of unique characters and the number of characters that have been matched so far int uniqueChars = map.Count; int matchedChars = 0; // initialize two pointers, left and right, to keep track of the current window int left = 0; int right = 0; // while the right pointer is less than the length of the string while (right < s.Length) { // if the character at the right pointer is in the hashmap if (map.ContainsKey(s[right])) { // decrement the count for that character map[s[right]]--; // if the count is now 0 (meaning we've matched all occurrences of that character), increment the matched characters counter if (map[s[right]] == 0) { matchedChars++; } } // increment the right pointer right++; // while the unique characters counter is equal to the matched characters counter (meaning we've found a window that contains all the characters in t) while (uniqueChars == matchedChars) { // if the current window is smaller than the minimum window, update the minimum window if (right - left < minWindowLength) { minWindowLength = right - left; minWindowStart = left; minWindowEnd = right; } // if the character at the left pointer is in the hashmap if (map.ContainsKey(s[left])) { // increment the count for that character map[s[left]]++; // if the count is now greater than 0 (meaning we've unmatched one occurrence of that character), decrement the matched characters counter if (map[s[left]] > 0) { matchedChars--; } } // increment the left pointer left++; } } // return the minimum window return minWindowLength == int.MaxValue ? "" : s.Substring(minWindowStart, minWindowEnd - minWindowStart); } }