76. Minimum Window Substring

We use hashtable and sliding window to solve this problem.

At first, we use an array count[256] to count the frequency of each character appeared in t.

Then we traverse s and update an array current[256] to count the frequency of each character in current substring of s.

For each characters c appeared in t, if count[c] <= current[c], then the current substring contains all characters appeared in t. Each time such candidate substring appears, we compare it with existing result to update the miminum window substring.

Note that there are three while structures in my code:

• The first assure we begin with a character which appears in t.
• The second minimize the candidate substring as short as possible. (For S = "ADOBECODEBANC", T = "ABC", if we don't have the second while, we will get BECODEBA instead of CODEBA during the traverse)
• The third assure the next round of traverse begin with a character which appears in t. (For S = "ADOBECODEBANC", T = "ABC", when the first round ends, we get the substring ADOBEC, apparently, the next round should begin with BEC rather than DOBEC).

public String minWindow(String s, String t) {
    int count[] = new int[256];
    for(int i = 0; i < t.length(); i++)
	count[t.charAt(i)]++;
    int sum = 0, slow = 0, minLength = s.length() + 1;
    String result = "";
    int current[] = new int[256];
    while( slow < s.length() && count[s.charAt(slow)] == 0 )  
	slow++;
    for(int i = slow; i < s.length(); i++) {
	int c = s.charAt(i);
	current[c]++;
	sum += (current[c] <= count[c] ? 1 : 0);
	if( sum == t.length() ) {
	    while( slow < i && current[s.charAt(slow)] > count[s.charAt(slow)] ) { 
	        current[s.charAt(slow)]--;
         	slow++;
	    }
	    if( i - slow + 1 < minLength ) {
	        minLength = i - slow + 1;
         	result = s.substring(slow, i + 1);    
	    }
   	    current[s.charAt(slow)]--;
	    slow++;
	    sum--;
	    while( slow < i && current[s.charAt(slow)] > count[s.charAt(slow)] ) { 
	        current[s.charAt(slow)]--;
	        slow++;
	    }
        }
    }
    return result;
}