LeetCode: Minimum Window Substring

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

//Ref: https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems
/**
-we use two pointers and hashmap
-left pointer and right pointer, right pointer advances till we find a window that contains all the
characters from t in s
-we note down the length of the window and advance the left pointer to check if we can find smaller window
-when
*/

public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
     
        for(char c : s.toCharArray()) {
            map.put(c, 0);
        }
     
        for(char c : t.toCharArray()) {
            if(map.containsKey(c)) {
                map.put(c, map.get(c)+ 1);
            } else {
                return "";
            }
        }
     
        int left = 0;
        int right = 0;
        int minleft = 0;
        int minLength = Integer.MAX_VALUE;
        int counter = t.length();
     
        while(right < s.length()) {
            char c1 = s.charAt(right);
            //if the character was present in target also, number of chars to be found is decreased
            if(map.get(c1) > 0) {
                counter--;
            }
            //decrease the count in hashmap because advancing the right pointer spans the window and includes this chracter in our new window
            map.put(c1, map.get(c1) - 1);
            right++;
         
            while(counter == 0) {
                if(minLength > right - left) {
                    minLength = right - left;
                    minleft = left;
                }
                //now shrink the window by advancing the left pointer
//if the left pointer points to the character from t, then increase the count in hashmap
//because we missed the character in our new window by shrinking the window
                char c2 = s.charAt(left);
                map.put(c2, map.get(c2) + 1);
                //if the count of the character in hashmap is more than 1, then we missed this character in our new window so increase the counter
                if(map.get(c2) > 0) {
                    counter++;
                }
                left++;
            }
        }
     
        return minLength == Integer.MAX_VALUE ? "" : s.substring(minleft, minleft + minLength);
    }
}