import java.util.*;

public class minWindowSubstring {
    public static void main(String[] args){
        minWindowSubstring obj = new minWindowSubstring();
        String s = "cabwefgewcwaefgcf";
        String t = "cae";
        System.out.println(obj.minWindow(s,t));
    }
    /* 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).
       Input: S = "ADOBECODEBANC", T = "ABC"
       Output: "BANC"
    * */
    // two pointers, sliding window algorithm
    private String minWindow(String s, String t){
        String res = "";
        if(s == null || t == null || s.length() < t.length()){
            return res;
        }
        int min = s.length();
        Map<Character, Integer> map = new HashMap<>();
        for(char ele: t.toCharArray()){
            map.put(ele, map.getOrDefault(ele,0)+1);
        }
        int counter = map.size();
        //int lo = 0, hi = 0;
        for(int lo=0, hi=0; hi < s.length(); hi ++){
            // move right pointer to find a valid substring
            if(map.containsKey(s.charAt(hi))){
                map.put(s.charAt(hi),map.get(s.charAt(hi)) - 1);
                if(map.get(s.charAt(hi)) == 0){
                    counter --;
                }
            }
            // move left pointer to find a min substring
            while(counter == 0 && lo <= hi){
                // pay attention to "<="
                // don't forget to update min's valueß
                if(hi - lo + 1 <= min){
                    res = s.substring(lo, hi+1);
                    min = hi - lo + 1;
                }
                if(map.containsKey(s.charAt(lo))){
                    map.put(s.charAt(lo), map.get(s.charAt(lo)) + 1);
                    if(map.get(s.charAt(lo)) > 0){
                        counter ++;
                    }
                }
                lo ++;
            }
        }
        return res;
    }
}