/*
https://leetcode.com/problems/minimum-window-substring
Runtime: 9 ms, faster than 69.12% of Java online submissions for Minimum Window Substring.
Memory Usage: 39 MB, less than 68.09% of Java online submissions for Minimum Window Substring.
*/
class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";
        HashSet<Character> allowed = new HashSet<>();
        int countdown = 0;
        int[] required = new int[256], found = new int[256], min = new int[] {Integer.MAX_VALUE, 0, 0};
        for (char c : t.toCharArray()) {
            if (allowed.add(c)) {
                ++countdown;
            }
            ++required[c];
        }
        LinkedList<Tuple> matched = new LinkedList<>();
        char[] chars = s.toCharArray();
        for (int index = 0; index < chars.length; index++) {
            char symbol = chars[index];
            if (allowed.contains(symbol)) {
                matched.addLast(new Tuple(index, symbol));
                if(++found[symbol] == required[symbol]) {
                    if(--countdown == 0) {
                        while(countdown == 0) {
                            Tuple left = matched.poll();
                            if (allowed.contains(left.symbol)) {
                                if (min[0] > index - left.index) {
                                    min[0] = index - left.index;
                                    min[1] = left.index;
                                    min[2] = index;
                                }
                                if(--found[left.symbol] < required[left.symbol]) {
                                    ++countdown;
                                }
                            }
                        }
                    }
                }
            }
        }
        return min[0] < Integer.MAX_VALUE ? s.substring(min[1], min[2] + 1) : "";
    }

    private static class Tuple {
        public int index;
        public char symbol;
        public Tuple(int index, char symbol) {
            this.index = index;
            this.symbol = symbol;
        }
    }
}