76. Minimum Window Substring Leetcode Java

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).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

The solution is very similar to 

30. Substring with Concatenation of All Words Leetcode

Similarly, we maintain a hashmap as the dictionary to store the counts of all chars in T.

Then, we maintain a window to make sure the window contains all the chars in T with the help of the dictionary(checking the count of each char and also keep tracking the effective count of all chars presented in S, eg.S="ABBBC", T= "ABC", Assume now left is at position 0, while right is at position 3,substring would be"ABBB" the effective count of char of T present in S is 2, because the count of B in T is 1, so the second B and the third B in S don't count towards to the effective count).

If the window contains all the chars in T, then update the minimum length and the result string if needed. Then move the left pointer until the window doesn't contain all chars in T, during this porcess, keep updating the result if needed. Then we can move the right pointer till the window is valid again, keep this process until the end of S.

Time complexity : O(n) because left and right pointer only move from 0 to end once, there is no backward movement at all.

 public String minWindow(String S, String T) {  
     if(S==null || T==null || S.length()==0 || T.length()==0) return "";  
     HashMap<Character, Integer> map=new HashMap<Character, Integer>();  
     for(int i=0;i<T.length();i++){  
       if(map.containsKey(T.charAt(i))){  
         map.put(T.charAt(i),map.get(T.charAt(i))+1);  
       }  
       else map.put(T.charAt(i),1);  
     }  
     int minL=S.length();  
     String res="";  
     int count=T.length();  
     int i=0;  
     int j=0;  
     while (i<S.length()){  
       char right=S.charAt(i);  
       if(map.containsKey(right)){  
         if(map.get(right)>0){  
           count--;  
         }  
         map.put(right,map.get(right)-1);  
       }  
       while(count==0 && j<=i){  
         if(i-j+1<=minL){  
           minL=i-j+1;  
           res=S.substring(j,i+1);  
         }  
         char left=S.charAt(j);  
         if(map.containsKey(left)){  
           if(map.get(left)>=0){  
             count++;  
           }  
          map.put(left,map.get(left)+1);  
         }  
         j++;  
        }  
        i++;  
       }  
     return res;  
   }