76.Minimum Window Substring

1- Slide Window

https://leetcode.com/problems/minimum-window-substring/discuss/26808/

1. Use two pointers: start and end to represent a window.
2. Move end to find a valid window.
3. When a valid window is found, move start to find a smaller window.

class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for(int i = 0; i < t.length(); i++){
            map[t.charAt(i)]++;
        }
        int count = t.length();
        int start = 0;
        int minStart = 0;
        int end = 0;
        int minLength = Integer.MAX_VALUE;
        while(end < s.length()){
            if(map[s.charAt(end)] > 0)
                count--;
            map[s.charAt(end)]--;
            end++;
            //The innder while loop will loop until we meet a char in t.
            while(count == 0){
                //Since we have end++, so the end have been update .so we don't need to use end - start + 1
                if(end - start < minLength){
                    minStart = start;
                    minLength = end - start ;
                }
                map[s.charAt(start)]++;
                if(map[s.charAt(start)] > 0){
                    count++;
                }
                start++;
            }
        }
        return (minLength == Integer.MAX_VALUE) ? "": s.substring(minStart, minStart + minLength);
    }
}