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: 76. Minimum Window Substring.

🤔 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: ""

💬 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:

👩🏽‍💻 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

💬 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:

👩🏽‍💻 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

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: 76. Minimum Window Substring.

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!