解题思路：
- 利用Array的index存两个string的词频。
- 什么情况下找到一个valid的字符；
- 什么情况下找到一个valid的完整字符串；
当找到这个字符串的时候：
- 跳过前面多余的字符；
- 更新需求，即最短长度；若更新了，记录开头和结尾；
- 跳过这个字符串的首字符，继续扫(found也要减一)。
====
看到题的第一反应，先数S中每个字母有多少个，以后后面一定要一个一个减掉。
我最初的想法：
s = “DADOBECODEBANC”
t = “ABC“
okay, scan S, start from the letter that also appears in T. here, we start from ADOBEC. this is an possible answer。
Then we skip the first A (cnt A--), start from B, BECODEBA. But when we arrives B, which locates between E and A, we skip the first B (cnt B --), since it will definitely gives shorter answer. keep working till the end.
因为先要存t的字频，之后查表，所以一定会用到hashTable/hashMap;
看了答案，答案用了hash的思想，但是只用array就存储了cnt的信息。
public class Solution {
public String minWindow(String s, String t) {
int[] sCnt = new int[255];
int[] tCnt = new int[255];
for (int i=0; i<t.length(); i++) {
tCnt[t.charAt(i)]++;
}
int start = 0;
int begin = -1, end = s.length();
int found = 0, minLen = s.length();
for (int i=0; i<s.length(); i++) {
char c1 = s.charAt(i);
sCnt[c1]++;
if(sCnt[c1] <= tCnt[c1]) found++;
if(found == t.length()) {
while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
sCnt[s.charAt(start)]--;
start++;
}
if(i-start < minLen) {
minLen = i-start;
begin = start;
end = i;
}
sCnt[s.charAt(start)]--;
start++;
found--;
}
}
return begin == -1 ? "" : s.substring(begin, end+1);
}
}
总结一下：直接在代码里写吧。
public class Solution {
public String minWindow(String s, String t) {
int[] sCnt = new int[255];
int[] tCnt = new int[255];
for (int i=0; i<t.length(); i++) {
tCnt[t.charAt(i)]++;
}
int start = 0;
int begin = -1, end = s.length();
int found = 0, minLen = s.length();
for (int i=0; i<s.length(); i++) {
char c1 = s.charAt(i);
sCnt[c1]++;
/** 如果算上这个字符后，数量不超过t中这个字符的数量，那么这个字符算是valid(即找到一个匹配的字符)；
*/
if(sCnt[c1] <= tCnt[c1]) found++;
/** 找到一个valid的字符串。
*/
if(found == t.length()) {
/** 这个字符串end一定是i。现在需要找到这个字符串的起始位置。
* 起始位置那个字符在s中出现的次数一定和在t中出现的次数一样多；
* 所有那些s中出现次数比t中多的，一定是多余的，从前往后扫，然后全部删掉。
* 记得每次从s中散掉的时候，s对这个字符的cnt也要减一。
*/
while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
sCnt[s.charAt(start)]--;
start++;
}
/** 更新minLen，如果更新了，那么记录下这个长度的起始点和终点。
*/
if(i-start < minLen) {
minLen = i-start;
begin = start;
end = i;
}
/** 把开头的start跳过，注意sCnt也要减一，继续扫。
*/
sCnt[s.charAt(start)]--;
start++;
found--;
}
}
return begin == -1 ? "" : s.substring(begin, end+1);
}
}
