// Runtime: 9 ms, beats 69.12 % of java submissions.
class Solution {
    public String minWindow(String s, String t) {
        int tLength = t.length();

        Map<Character, Integer> map = new HashMap<>();
        int[] tCount = new int[tLength];

        int charCount = 0;
        for (int i = 0; i < tLength; i++) {
            char c = t.charAt(i);
            Integer ix = map.get(c);
            if (ix == null){
                ix = charCount++;
                map.put(c, ix);
            }
            tCount[ix] += 1;
        }

        int[] sArray = new int[s.length()];
        for (int i=0; i < s.length(); i++){
            Integer ix = map.get(s.charAt(i));
            sArray[i] = ix != null ? ix: -1;
        }

        int minLength = Integer.MAX_VALUE;
        int minPos = 0;

        Deque<Integer> idx = new ArrayDeque<Integer>();
        int[] presence = new int[charCount];
        int matchCount = 0;

        for (int i = 0; i < sArray.length; i++) {
            int c = sArray[i];
            if (c == -1) continue;

            int pb = presence[c];

            idx.addLast(i);
            presence[c] += 1;

            for (;;) {
                int first = sArray[idx.getFirst()];
                if (presence[first] <= tCount[first]) break;

                idx.removeFirst();
                presence[first] -= 1;
            }

            if (presence[c] > pb && presence[c] <= tCount[c]) {
                matchCount++;
            }

            if (matchCount == tLength) {
                int len = idx.getLast() - idx.getFirst() + 1;
                if (len < minLength) {
                    minLength = len;
                    minPos = idx.getFirst();
                }

                int first = sArray[idx.getFirst()];
                idx.removeFirst();
                presence[first] -= 1;

                matchCount--;
            }
        }

        if (minLength == Integer.MAX_VALUE) return "";

        return s.substring(minPos, minPos + minLength);
    }
}