76. Minimum Window Substring

class Solution {
    public String minWindow(String s, String t) {
        int startIndex = 0, endIndex = -1;
        int[] targetMap = new int[128]; // 注意题目仅提及英文字母，未限制大小写，所以申请容量为 128 的数组
        int targetChars = 0;
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (targetMap[c]++ == 0) {
                targetChars++;
            }
        }

        int[] windowMap = new int[128];
        int matchChars = 0;
        int i = 0;
        for (int j = 0; j < s.length(); j++) { // window: [i, j]
            char c = s.charAt(j);
            if (++windowMap[c] == targetMap[c]) {
                matchChars++;
            }

            while (matchChars == targetChars) {
                if (endIndex == -1 || j - i < endIndex - startIndex) {
                    startIndex = i;
                    endIndex = j;
                }

                char leftmost = s.charAt(i);
                if (windowMap[leftmost]-- == targetMap[leftmost]) {
                    matchChars--;
                }
                i++;
            }
        }

        return endIndex == -1 ? "" : s.substring(startIndex, endIndex + 1);
    }
}

References

76. Minimum Window Substring
剑指 Offer II 017. 含有所有字符的最短字符串