# 76. Minimum Window Substring

Hello, reader 👋🏽 ! Welcome to day 22 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: <a href="https://leetcode.com/problems/minimum-window-substring/" target="_blank">76. Minimum Window Substring</a>.

<hr />

## 🤔 Problem Statement
- 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 "".
- E.g.:
  - `s = "ADOBECODEBANC", t = "ABC"`  -> minimum window substring: `"BANC`"
  - `s = "ababac" t = "aba"` -> minimum window substring: `"abac"`
  - `s = "" t = "abc"` -> minimum window substring: `""`
<hr />

## 💬 Thought Process - Sliding Window O(m*n)
- The most intuitive approach that comes to our minds is to maintain pointers- left and right- representing the start and end window respectively.
- A hash table can be used to keep track of all the characters and occurrences of string `t`.
- We keep adding new characters (hence expanding the window) until the window in string `s` covers all the strings in string `t`.
- Once a window is formed, we update the current substring `s.substring(left, right+1)` if the current substring has a length smaller than the previously found substring.
- We also try to reduce the window from the left side and try to find a smaller window within `[left, right]`. 
  - _This can be the case if there are multiple occurrences of one or more characters within the window._
  - E.g.: `ababac` is a window for `aba`, but this window can be reduced to -> `babac` and `abac` to find the minimum window substring.
- Once reducing the left pointer does not generate a window, we update the right pointer and continue until the end of string.
- The image below gives a rough idea of how this approach works:
    ![approach-one.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1666456680429/zb4dgLpGg.png align="left")


### 👩🏽‍💻 Solution - Sliding Window O(m*n)
- Below is the code for the above discussed brute force approach.

```
class Solution {
    public String minWindow(String s, String t) {
        if(s == null || s.length() == 0) {
            return "";
        }
        
        String substring = "";
        int m = s.length(), n = t.length();
        Map<Character, Integer> mapT = new HashMap();
        
        for(int i = 0; i<n; i++) {
            char ch = t.charAt(i);
            mapT.put(ch, mapT.getOrDefault(ch, 0) + 1);
        }
        
        int left = 0, right = 0;
        
        Map<Character, Integer> mapS = new HashMap();
        while(right < m) {
            char ch = s.charAt(right);
            if(!mapS.containsKey(ch)) {
                mapS.put(ch, 0);
            }
            int c = mapS.get(ch);
            mapS.put(ch, c+1);

            boolean isEqual = checkIfEqual(mapT, mapS);
            if(isEqual) {
                while(left <= right && checkIfEqual(mapT, mapS)) {
                    String newS = s.substring(left, right+1);
                    if(substring.isEmpty() || 
                      newS.length() < substring.length()) {
                        substring = newS;
                    }
                    removeChar(mapS, s.charAt(left));
                    left++;
                }
            }
            right++;
        }
                
        return substring;
    }
    
    
    private void removeChar(Map<Character, Integer> map, char left) {
        if(map.containsKey(left)) {
            if(map.get(left) == 1) {
                map.remove(left);
            }
            else {
                int c = map.get(left);
                map.put(left, c-1);
            }
        }
    }
    
    private boolean checkIfEqual(Map<Character, Integer> m1, 
        Map<Character, Integer> m2) {
        for(char ch: m1.keySet()) {
            if(m2.containsKey(ch)) {
                if(m2.get(ch) < m1.get(ch)) {
                    return false;
                }
            }
            else {
                return false;
            }
        }
        
        return true;
    }
}
```
```
  Time Complexity: O(m*n)
    - m = length of string s
    - n = length of string t
      - In the worst case, we will be iterating through the string of length `O(m)` the keys in hash map which takes O(n).
Space Complexity: O(m + n)
  - m = length of string s
  - n = length of string s
      - We use a map to hold the count of characters
```

<hr />

## 💬 Thought Process - Sliding Window
- The above solution is not great since we are doing repeated work that can be avoided.
- E.g.: let's take an example with the string `s = "ababac" t = "abc"`.
  - The first character in the window is `a`. We match this window's character count with that of a string `t`'s count. Since they are different we continue.
  - The second character in the window is `b`. Now when we match the character's count with that of string `t`, we do repeated work by checking for `a`'s frequency again. 
  - And this continues until `ababa` and  `ababac`, where we compare the frequency for `ababa` again for both the windows with string `t`.
- Another unnecessary memory wastage in the above approach is keeping track of intermediate window strings. This is very costly (at least for languages like Java).

- This can be reduced to `O(m)` easily by using of a count variable that keeps track whether of not a matching window was found or not.
- In the below approach we will eliminate re-checking the character count for every window and do it only when the window expands or contracts.
- We also avoid storing intermediate answers, and only keep track of start and end of every window.

- We keep the goal to be formed as the unique characters that can be found in string `t`. This is equal to the size of the hash table that holds character count -> `goalUniqueCount`.
- Then we iterate through string `s` using left and right pointers as well as a count variable that tracks if the same number of unique characters are in a window as in string `t`. 
- Every time the `s[right]` character and `t[right]` has the same frequencies, we increment the unique character formed in the window -> `windowUniqueCount`.
- Once the `goalUniqueCount == windowUniqueCount`, we update the start and end of the window if this window is smaller than the previous window. 
- We also repeat the process of reducing the size of the window by moving the left pointer.
  - We reduce the left most character count in the map and check if the `goalUniqueCount` and `windowUniqueCount` still matches. If yes, we update the window start, end indices.
- Once reducing the left pointer no longer matches the `goalUniqueCount`, we increment the right pointer and continue the process.

- The image below gives a rough idea of how this approach works:
    ![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1666457956209/Xvz-FnS5j.png align="left")

### 👩🏽‍💻 Solution - Sliding Window O(m + n)
- Below is the code for the above discussed sliding window approach.

```
class Solution {
    public String minWindow(String s, String t) {
        if(s == null || s.length() == 0) {
            return "";
        }
        
        String substring = "";
        int m = s.length(), n = t.length();
        Map<Character, Integer> mapT = new HashMap();
        
        // O(n)
        for(int i = 0; i<n; i++) {
            char ch = t.charAt(i);
            mapT.put(ch, mapT.getOrDefault(ch, 0) + 1);
        }
        
        // This is the number of unique characters in T 
        // that are required in the min substring
        int numUniqueCharsRequired = mapT.size();
        
        int left = 0, right = 0, numUniqueCharsFormed = 0;
        Map<Character, Integer> mapS = new HashMap();
        
        int smallestWindow = -1;
        int start = -1;
        int end = -1;
        
        while(right < m) {
            char ch = s.charAt(right);
            if(!mapS.containsKey(ch)) {
                mapS.put(ch, 0);
            }
            int c = mapS.get(ch)+1;
            mapS.put(ch, c);
    
            if(mapT.containsKey(ch) && mapT.get(ch) == c) {
                numUniqueCharsFormed++;
            }
            
            while(left <= right && numUniqueCharsFormed == numUniqueCharsRequired) {
                char leftC = s.charAt(left);
                int currWindow = right - left + 1;
                if(smallestWindow == -1 || currWindow < smallestWindow) {
                    smallestWindow = currWindow;
                    start = left;
                    end = right;
                }
                    
                mapS.put(leftC, mapS.get(leftC)-1);
                // check if the removed left most char
                // still matches in the current window
                if(mapT.containsKey(leftC) && mapT.get(leftC) > mapS.get(leftC)) {
                    numUniqueCharsFormed--;
                }
                
                // increment the window from the left
                left++;
            }
            
            right++;
        }
                
        return smallestWindow == -1 ? "" : s.substring(start, end+1);
    }
}
```

```
Time Complexity: O(m + n)
  - m = length of string s
  - n = length of string s
     - We traverse both the strings from start to end. In the worst case we could go through the string s twice 
Space Complexity: O(m + n)
  - m = length of string s
  - n = length of string s
      - We use a map to hold the count of characters
```


<hr />

- There's another optimisation that could be done for this question (src: LeetCode). Instead of finding the window on the entire string `s`, we can form windows using only those characters that are present in string `t`.
- You can find the code for this question in the GitHub repo here: <a href="https://github.com/bharati-21/daily-problem-solving/tree/main/76-minimum-window-substring">76. Minimum Window Substring</a>.

<hr />

## Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!