76. Minimum Window Substring

Problem Statement

Pattern: Related: Smallest Distinct Window

---

Solution

public String minWindow(String s, String t) {
	
	// prepare dict
	Map<Character, Integer> dict = new HashMap<>();
	for(char c : t.toCharArray()) dict.put(c, dict.getOrDefault(c, 0) + 1);
	
	int required = dict.size(), formed = 0;     // required : no. of uniqe ch's in string
	int l = 0, r = 0;
	int[] ans = {-1, l, r};                     // size, l, r
	
	Map<Character, Integer> window = new HashMap<>();
	
	// sliding window
	while(r < s.length()) {
		
		// add char to window
		char curr = s.charAt(r);
		window.put(curr, window.getOrDefault(curr, 0) + 1);
		if(dict.containsKey(curr) && dict.get(curr).equals(window.get(curr))) formed++;
		   
		// contract window till invalid
		while(l <= r && formed == required) {   // check if valid window
			char prev = s.charAt(l);
			
			// update ans if window smaller
			if(ans[0] == -1 || r - l + 1 < ans[0]) {
				ans[0] = r - l + 1;
				ans[1] = l;
				ans[2] = r;
			}
			
			// remove prev char from window
			window.put(prev, window.get(prev)-1);
			// update formed
			if (dict.containsKey(prev) && window.get(prev).intValue() < dict.get(prev).intValue())
				formed--;
			
			// shift l fwd
			l++;
		}
		
		// shift r fwd 
		r++;
	}
	return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}

TC : $O(|S|+|T|)$ SC : $O(|S|+|T|)$

Notes

• This is basically a slightly complex sliding window problem, a window which needs to know what is the freq of each character in it window , and the required minimum freq of each character dict.
• We keep expanding a window, and once it is valid (formed == required) we start contracting it and updating the answer till its invalid (formed != required)
• We return minimum substring

Optimised Solution

filtered_S is the S string without the extra characters not present in T. Checkout the solution