// 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;

        LinkedList<Integer> idx = new LinkedList<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 first = idx.isEmpty() ? -1: sArray[idx.getFirst()];

            while (idx.size() > 2 && presence[first] > tCount[first]) {
                idx.removeFirst();
                presence[first] -= 1;
                first = sArray[idx.getFirst()];
            }

            if (first == c && presence[first] >= tCount[first]) {
                idx.removeFirst();
            }
            else {
                if (presence[c] < tCount[c]) matchCount++;
                presence[c] += 1;
            }
            idx.add(i);

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

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

                matchCount--;
            }
        }

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

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