Sliding window

76. Minimum Window Substring

https://labuladong.gitbook.io/algo/mu-lu-ye/hua-dong-chuang-kou-ji-qiao-jin-jie

class Solution {
    public String minWindow(String s, String t) {
        int left=0;
        int right = 0;
        Map<Character, Integer> tMap = new HashMap<>();
        for(int i=0; i<t.length(); i++){
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0)+1);
        }
        
        int validChar=0;
        // [start, end)
        int resultStart = 0;
        int resultEnd = 0;
        while(right<s.length()){
            char c = s.charAt(right);
            if(tMap.containsKey(c)){
                if(tMap.get(c)>0) validChar++;
                // need to substract even if the value is 0
                tMap.put(c, tMap.get(c)-1);
            }
            right++;
            
            // move the left pointer
            while(validChar==t.length()){
                if(resultEnd-resultStart==0 || right-left<resultEnd-resultStart){
                    resultEnd = right;
                    resultStart = left; 
                }
                
                c = s.charAt(left);
                left++;
                if(tMap.containsKey(c)){
                    if(tMap.get(c)==0) validChar--;
                    tMap.put(c, tMap.get(c)+1); 
                }
            }
        }
        // remember: substring()
        return s.substring(resultStart, resultEnd);
    }
}