/*
Runtime: 16 ms, faster than 63.17% of Java online submissions for Minimum Window Substring.
Memory Usage: 38.4 MB, less than 90.43% of Java online submissions for Minimum Window Substring.
*/

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() == 0) return "";

        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        Map<Character, Integer> reqMap = new HashMap<>();
        for (int i = 0; i < tarr.length; i++) {
            int c = reqMap.getOrDefault(tarr[i], 0);
            reqMap.put(tarr[i], ++c);
        }

        Map<Character, Integer> window = new HashMap<>();
        int target = reqMap.size();
        int front = 0;
        int back = 0;
        int found = 0;

        int minLength = -1;
        int minStart = -1;
        while(front < sarr.length) {
            Integer required = reqMap.get(sarr[front]);
            if (required != null) {
                int current = window.getOrDefault(sarr[front], 0);
                window.put(sarr[front], ++current);
                if (current == required)
                    found++;
            }

            while (found == target && back <= front) {
                int currentLen = front - back + 1;

                if (minLength == -1 || currentLen < minLength) {
                    minLength = currentLen;
                    minStart = back;

                }

                required = reqMap.get(sarr[back]);
                if (required != null) {
                    int current = window.get(sarr[back]);
                    window.put(sarr[back], --current);
                    if (current < required)
                        found--;
                }
                back++;
            }
            front++;
        }

        if (minLength == -1) return "";
        return s.substring(minStart, minStart + minLength);
    }
}