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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
- If there is no such window in S that covers all characters in T, return the empty string "".
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Solution
- 关于字母出现的频次问题用
hashtable，且这里的字符其实只有Ascii码里面的前128个字符，所以使用int[128]。 - 首先统计
T string，int[128]上就记录了每一个字符的个数。 - 要想在O(n)的时间， 用到滑动窗的思路。那么定义这个窗口，窗口的左边界到右边界内的字符包含了
T string中所有字符，并且左边界一定不能再向右移动。 - 同时，定义一个
counter来记录在S string中找到了多少个T string的字符，当counter = s.length表示找到了所有字符，但有可能包含多余的字符，并不是最小集合。此时就需要移动左边界。具体逻辑如下：
定义counter，初始化距离为
s.length，在S string中滑动窗口时 （左右边界初始都为0）：
1）向右滑动右边界时，每增加一个字母，如果其为T string中字符，且出现频次不超过T string中该字母的频次，那么counter - 1。
2）向右滑动左边界时，每移除一个字母，如果其为T string中字符，且出现频次不超过T string中该字母的频次，那么counter + 1。判断右边界：
1） 如果这个位置的值> 0，说明这个位置是T string中字符，并且现在窗中个数还不足，counter --。
2） 如果这个位置的值<= 0，那么这个位置为以下情况，不操作：
* 不是T string中的字符。
* 是T string中的字符，但是窗中这个字符太多，以至于为负。当前counter为0，说明窗中包含了所有字符，但是可能有多的，尝试移动左边界，过程中会
update counter，一旦counter != 0, 则停止移动左边界：
1） 如果左边界在int[128]上对应位置值== 0，说明此字符是集合需要的字符（否则这个位置的值该为负），并且个数刚刚好，counter ++（因为其会被移除，则update counter）
2） int[128]上对应位置值++1且 右移左边界。
Time: O(n), Space O(1)
Code
class Solution {
public String minWindow(String s, String t) {
int sLen = s.length ();
int tLen = t.length ();
// S is shorter than T, can never find such substring
if (sLen < tLen)
{
return "";
}
// Use hashtable to track occurance of characters in T
// and use a viable [count] to track how many characters are found in S
// Only while count == length of T, means it is a substring which contains all characters in T
// But, it might also contain characters which are not in T.
int left = 0, right = 0;
int head = 0; // it requires to return the min substring, use head to tracker the left pointer of min substring;
int count = tLen; // initial count == tLen. count -- while find a character in S, while count == 0, means find all characters
int minLen = Integer.MAX_VALUE;
int[] tracker = new int [256];
// loop through T to get the occurance of characters
for (char ch : t.toCharArray ())
{
tracker [ch] ++;
}
// loop through S, to find the substring while contains all characters in T
while (right < sLen)
{
// if the value is > 0, means it is the character in T (initially it is 0)
if (tracker [s.charAt (right)] > 0)
{
count --;
}
tracker [s.charAt (right)] --;
right ++; // move right pointer
// found all characters, try to move left pointer
while (count == 0)
{
// update the min substring head and length
if (right - left < minLen)
{
minLen = right - left;
head = left;
}
// while == 0, it's the character in T and the occurance is also satisfied the requirement
if (tracker [s.charAt (left)] == 0)
{
count ++;
}
// move left pointer
tracker [s.charAt (left)] ++;
left ++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring (head, head + minLen);
}
}
