76. Minimum Window Substring.java

class Solution {
    public String minWindow(String s, String t) {
        int min = Integer.MAX_VALUE;
        int minStart = 0;
        int[] map = new int[128];
        for (char c: t.toCharArray()) {
            map[c]++;
        }
        int start = 0;
        int end = 0;
        int count = t.length();
        while (end < s.length()) {
            if (map[s.charAt(end)] > 0) {
                count--;
            }
            map[s.charAt(end)]--;
            end++;
            
            while (count == 0) {
                if (end - start < min) {
                    min = end - start;
                    minStart = start;
                }
                map[s.charAt(start)]++;
                if (map[s.charAt(start)] > 0) {
                    count++;
                }
                start++;
            }
        }
        return min == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + min);
    }
}