LeetCode Q76: Minimum Window Substring (hard*)

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 empty string "".

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

This is a typical "substring" problem. People gave many beautiful solutions. 

Solution 1

1. Initialize a vector called remaining, which contains the needed matching numbers of each character in s.
2. If there are still characters needed to be contained (increment i in this case), decrease the matching number of that character and check if it is still non-negative. If it is, then it is the character in t, so decrease the total required number required.
3. If there is no more characters required (increment start in this case), record min andleft if a smaller length is found. Recover the number of this character in the remainingand if it is a character in t increase required.

	string minWindow(string s, string t) {
	if (s.size() == 0 || t.size() == 0) return "";
	vector<int> remaining(128, 0);
	// Setup a counter to track how many characters in t are not met.
	int required = t.size();
	for (int i = 0; i < required; i++)
	remaining[t[i]]++;
	// left is the start index of the min-length substring ever found
	int min = INT_MAX, start = 0, left = 0, i = 0;
	while(i <= s.size()) {
	if(required){
	// For each character in s, we decrease remaining array.
	// Since we only initialized remaining array for characters in t,
	// So, all other characters not in t will make remaining array to be negative.
	remaining[s[i]]--;
	// If remaining array is still non-negative, means, character s[i] is a character
	// in t. Use >= to include cases where there are duplicate characters in t.
	if(remaining[s[i]]>=0)
	required--;
	i++;
	}else{
	// When all characters in t are met, check whether the shortest met ever.
	if(i-start<min){
	min=i-start;
	left=start;
	}
	// remove the leftmost character in current substring and move left bound one step ahead.
	remaining[s[start]]++;
	if(remaining[s[start]]>0)
	required++;
	start++;
	}
	}
	return min == INT_MAX? "" : s.substr(left, min);
	}

view raw Q76MinimumWinSubstring1.cpp hosted with ❤ by GitHub

Solution 2 (Similar to solution 1, but more concise.)

	string minWindow(string s, string t) {
	vector<int> map(128,0);
	for(auto c: t) map[c]++;
	int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
	while(end<s.size()){
	if(map[s[end++]]-->0) counter--; //in t
	while(counter==0){ //valid
	if(end-begin<d) d=end-(head=begin);
	if(map[s[begin++]]++==0) counter++; //make it invalid
	}
	}
	return d==INT_MAX? "":s.substr(head, d);
	}

view raw Q76-2.cpp hosted with ❤ by GitHub

Template that can solve almost all substring problems

	int findSubstring(string s){
	vector<int> map(128,0);
	int counter; // check whether the substring is valid
	int begin=0, end=0; //two pointers, one point to tail and one head
	int d; //the length of substring
	for() { /* initialize the hash map here */ }
	while(end<s.size()){
	if(map[s[end++]]-- ?){ /* modify counter here */ }
	while(/* counter condition */){
	/* update d here if finding minimum*/
	//increase begin to make it invalid/valid again
	if(map[s[begin++]]++ ?){ /*modify counter here*/ }
	}
	/* update d here if finding maximum*/
	}
	return d;
	}

view raw Q76-3.cpp hosted with ❤ by GitHub

The code of solving Longest Substring with At Most Two Distinct Characters is below:

	int lengthOfLongestSubstringTwoDistinct(string s) {
	vector<int> map(128, 0);
	int counter=0, begin=0, end=0, d=0;
	while(end<s.size()){
	if(map[s[end++]]++==0) counter++;
	while(counter>2) if(map[s[begin++]]--==1) counter--;
	d=max(d, end-begin);
	}
	return d;
	}

view raw Q76-4.cpp hosted with ❤ by GitHub

	int findSubstring(string s){
	vector<int> map(128,0);
	int counter; // check whether the substring is valid
	int begin=0, end=0; //two pointers, one point to tail and one head
	int d; //the length of substring
	for() { /* initialize the hash map here */ }
	while(end<s.size()){
	if(map[s[end++]]-- ?){ /* modify counter here */ }
	while(/* counter condition */){
	/* update d here if finding minimum*/
	//increase begin to make it invalid/valid again
	if(map[s[begin++]]++ ?){ /*modify counter here*/ }
	}
	/* update d here if finding maximum*/
	}
	return d;
	}

view raw Q76-3.cpp hosted with ❤ by GitHub

The code of solving Longest Substring Without Repeating Characters is below:

	int lengthOfLongestSubstring(string s) {
	vector<int> map(128,0);
	int counter=0, begin=0, end=0, d=0;
	while(end<s.size()){
	if(map[s[end++]]++>0) counter++;
	while(counter>0) if(map[s[begin++]]-->1) counter--;
	d=max(d, end-begin); //while valid, update d
	}
	return d;
	}

view raw Q76-5.cpp hosted with ❤ by GitHub