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
        Map map = 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_map target;
        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);
    }
}