28 Sep 2023, 9:50 PM
28 Sep 2023, 9:50 PM

15. Minimum Window Substring

#leetcode/76

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

The test cases will be generated such that the answer is unique.

Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Solution

Solution in C++ using two hash maps

Here's the process:

  1. Create arrays t_map and s_map of size 128 to store character frequency information. t_map stores the frequency of characters in string t, while s_map stores the frequency of characters in the current window of string s.
  2. Populate t_map with the frequency of characters in string t.
  3. Iterate through the characters in string s using two pointers, low (left) and high (right).
  4. For each character at index high, check if it exists in t_map. If not, skip it.
  5. If the character exists in t_map, update its frequency in s_map and check if the frequency in s_map is less than or equal to the frequency in t_map. If it is, increment t_counter to keep track of how many characters from t have been found.
  6. When t_counter reaches n (meaning all characters from t have been found in the current window), check if the current window's length (high - low + 1) is smaller than the current minimum length (minLength). If it is, update minLength and minStart with the current window's information.
  7. Shrink the window from the left side (increment low) and update s_map and t_counter accordingly to search for a smaller window.
  8. Repeat steps 3-7 until you have iterated through the entire string s.
  9. After the loop, check if a valid minimum window was found (i.e., minLength is still equal to its initial value). If a valid minimum window exists, return that window using s.substr(minStart, minLength). If no valid window exists, return an empty string.
string minWindow(string s, string t) {
	int minLength = INT_MAX, minStart = 0, m = s.size(), n = t.size(), t_counter = 0;
	array<int, 128> t_map = {};
	array<int, 128> s_map = {};
	string res;

	//get the frequency of each element in t
	for(char c : t)
		t_map[c]++;

	for(int low = 0, high = 0; high < m; high++) {
		//if the current character is not in t, skip!
		if(!contains(t_map, s[high]))
			continue;
		//otherwise, there are some checks to do...
		
		//first, update the frequency of the character
		s_map[s[high]]++;
		//increment t_counter if we are not in sur plus of s[high]
		if(s_map[s[high]] <= t_map[s[high]])
			t_counter++;
		//we have found all the needed characters!
		while(t_counter == n) {
			//maybe it's the minimum substring so far...
			if(high - low + 1 < minLength) {
				//yes, it's the minimum! Remind its length..
				minLength = high - low + 1;
				//remind the start position of the string
				minStart = low;
			}
		
			/* 
				now we try to shrink the substring from left,
				hoping to find a smaller string...
			*/
			
			//update the frequency of the character
			s_map[s[low]]--;
			//if we haven't enough characters anymore, decrease t_counter
			if(contains(t_map, s[low]) && s_map[s[low]] < t_map[s[low]])
				t_counter--;
			low++;
		}
	}
	return minLength != INT_MAX ? s.substr(minStart, minLength) : "";
}

bool contains(const array<int, 128>& map, const int& val) {
	return map[val] >= 1;
}