Leetcode — 76. Minimum Window Substring

The link to the problem: https://leetcode.com/problems/minimum-window-substring/

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Constraints:

• 1 <= s.length, t.length <= 105
• s and t consist of English letters.
• Could you find an algorithm that runs in O(n) time? (In my opinion, this is an interview type question. It is possible that they ask you to solve in O(n) even if you found another solution to solve the problem)

Example - 
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC" 
windows like ADOBEC, BECODEBA, CODEBA, BANC, etc. are all valid, but BANC has the minimum length.

Thoughts:

It is hard to immediately know how to solve this type of problem if this is your first time seeing it.

The first thought that came into my mind is using brute force that takes O(n²)
If we use 2 pointers, i and j, to represent our starting and ending points of our window. We keep moving j to the right until we found a valid window when the starting point is at i.

The code will be like below:

public String minWindow(String s, String t) {
        if(t.length()>s.length())
            return "";
        int[] map = new int[256];
        for(char c:t.toCharArray())
            map[c]++;
        
        String rst = "";
        int slen = s.length(), tlen = t.length();
        for(int i=0;i<slen;i++)//start
        {
            if(map[s.charAt(i)]==0)
                continue;
            for(int j=i+tlen;j<=slen;j++) //end
            {
                String temp = s.substring(i,j);
                if(checkValid(map, temp, t))
                {
                    if(rst.length()==0 || (j-i)<rst.length())
                        rst = temp;
                    break; // since we have found the min len of the substring starting at i
                }
            }
        }
        return rst;
    }
    public boolean checkValid(int[] map, String s, String t){
        int[] tempMap = new int[256];
        for(char c:s.toCharArray())
            tempMap[c]++;
        for(int k=0;k<256;k++)
        {
            if(map[k]>tempMap[k])
                return false;
        }
        return true;
    }

⚠️Time complexity is O(n²) since we have a loop for each starting position i to find us the nearest ending point j. The code will run successfully for most of the cases on Leetcode. However, the code will fail in the last 2 cases due to Time Limit Exceeded.

How can we improve our time complexity?

In the previous code, we will keep moving j to form a substring that starts at i and ends at j until we find the first j that satisfied the window condition. After finding j, we will move i forward and start over again to find the best j for this starting position.

We found that some of the checking actions are kind of duplicated and meaningless. For example, when the starting point is i1, we already found the string in [i1, j1] is valid. However, when we need to keep checking over and over again to find [i2,j1] is also valid.

What we should do is make good use of the first valid window we found instead of going all over again.

We keep expanding the window to the right using pointer j until we found a valid window. Once we found it, we can try to move our pointer i to the right to shrink the window. Once the window becomes invalid when we shrink the window, we should expand the window till we found the next valid window. And keep repeating …. expanding -> shrinking -> expanding -> shrinking …

Let’s see a series of graphs below for a better understanding of the idea —

👉 The goal is to find the minimum window that contains “ABC” in “ADOBECODBANC”

Code Logic:

The pointers i and j start at index 0.
1. We keep i at the original point and keep forwarding j until we find a valid window.
Since we know that j only moves forward if necessary (i.e., it will move forward if the current window is not valid), hence we can try to move i to see if it is possible to get a valid window with a smaller size.
2. We keep moving i until the current valid window is no longer valid.
3. Repeat 1 and 2.

step 1: i and j starts at 0

step 2: j stops forwarding when it founds a valid window “ADOBEC”

step 3: i forward one position and stops, since now the window is not valid again.

step 4: This time, j moves forward till the end to found another valid window. Let’s see if we can move i to make the current valid window smaller.

step 5: This time when we move i forward one position, the window is still valid. We can just keep moving i forward to shrink the window. 👌

step x: We keep getting our new valid window while i moving forward.

While i reaches here, we found that the current window is not valid anymore. However, we found that we fail to use j to open the window since j already reaches the end. Terminate the code.

Below is the 3ms code that beats 98%:

public String minWindow(String s, String t) {
        if(s.length()<t.length())
            return "";
        int[] map = new int[256];
        for(char c: t.toCharArray())
            map[c]++;
        //the number of chars we need to find 
        int num = t.length(); 
        int[] validWindow = new int[]{-1,-1};
        int minLen = s.length()+1;
        int i = 0, j = 0;
        while(j<s.length())
        {
            if(map[s.charAt(j)]>0)
                num--; //found 1 qualified number 
            map[s.charAt(j)] --; 
            //num == 0 means now the window is valid 
            //try to see if we can move i to shrink the window
            while(num==0) 
            {
                if((j-i+1) < minLen)
                {
                    validWindow[0] = i;
                    validWindow[1] = j;
                    minLen = j-i+1;
                }
                map[s.charAt(i)]++;
                if(map[s.charAt(i)]>0)
                    num++;
                i++;
            }
            j++;
        }
        return validWindow[0]==-1?"":
                s.substring(validWindow[0], validWindow[1]+1);
    }

Time complexity: O(n)
Space complexity: O(1)