Leetcode - Minimum Window String

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

[分析] 首先明确下题意，在S中寻找包含完整T字符串的最短子串，T中字符可能有重复。类似Longest Substring Without Repeating Characters， 思路也是借助哈希表和两指针表示的滑动窗口。右指针不断往前走，当前窗口包含整个T时前移左指针以缩减窗口使得窗口是在当前右指针位置处的最小窗口，缩减规则：左指针指向的字符非T中字符或者窗口中该字符个数多于T中的个数。缩减后窗口大小若小于全局最小窗口则更新全局最小窗口相关变量。实现中 i, j 表示当前考察窗口的左右边界指针，left, right表示满足条件的最小窗口的左右边界指针，变量counter表示窗口包含T字符的个数。needToFind表存储了T中每个字符出现的个数，hasFound表存储当前窗口包含各待找字符的个数。

[ref]
http://www.cnblogs.com/TenosDoIt/p/3461301.html

    public String minWindow(String s, String t) {
        if (s == null || t == null) return "";
        int counter = 0;
        int sLen = s.length(), tLen = t.length();
        int[] needToFind = new int[256];
        for (int i = 0; i < tLen; i++)
            needToFind[t.charAt(i)]++;
        int[] hasFound = new int[256];
        int left = -1, right = -1;
        int minLen = sLen + 1;
        for (int i = 0, j = 0; j < sLen; j++) {
            char charj = s.charAt(j);
            if (needToFind[charj] == 0) continue;
            hasFound[charj]++;
            if (hasFound[charj] <= needToFind[charj]) counter++;
            if (counter >= tLen) {
                while (needToFind[s.charAt(i)] == 0 || (hasFound[s.charAt(i)] > needToFind[s.charAt(i)])) {
                    if (needToFind[s.charAt(i)] > 0)
                        hasFound[s.charAt(i)]--;
                    i++;
                }
                if (j - i + 1 < minLen) {
                    left = i;
                    right = j;
                    minLen = j - i + 1;
                }
            }
        }
        return left != -1 ? s.substring(left, right + 1) : "";
    }