Minimum Window Maximum

Problem Statement:

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 testcases will be generated such that the answer is unique.

Example 1:

Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC” Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:

Input: s = “a”, t = “a” Output: “a” Explanation: The entire string s is the minimum window.

Example 3:

Input: s = “a”, t = “aa” Output: "" Explanation: Both ‘a’s from t must be included in the window. Since the largest window of s only has one ‘a’, return empty string.

Constraints:

m == s.length n == t.length 1 <= m, n <= 10^5 s and t consist of uppercase and lowercase English letters.

Solution:

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
 
        int counter = map.size(); // Check whether the substring is valid
        int start = 0, end = 0; // Two pointers, one point to tail and one head
        int minLength = Integer.MAX_VALUE; // The length of the substring
        int head = 0; // To store the starting index of the result substring
 
        while (end < s.length()) {
            char cEnd = s.charAt(end);
            
            if (map.containsKey(cEnd)) {
                map.put(cEnd, map.get(cEnd) - 1);
                if (map.get(cEnd) == 0) {
                    counter--; // Modify counter here
                }
            }
 
            while (counter == 0) { // Counter condition
                int windowSize = end - start + 1;
                if (windowSize < minLength) {
                    minLength = windowSize; // Update minLength here if finding minimum
                    head = start;
                }
				
				//Restore the variables, for shrinking window
                char cStart = s.charAt(start);
                if (map.containsKey(cStart)) {
                    map.put(cStart, map.get(cStart) + 1);
                    if (map.get(cStart) > 0) {
                        counter++; // Modify counter here
                    }
                }
                start++; // Increase begin to make it invalid/valid again
            }
            end++;
        }
 
        return minLength == Integer.MAX_VALUE ? "" : s.substring(head, head + minLength);
    }
}