题目:
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中所有的字母。
思路:
i,j表示S串的起点与终点;
一个数组保存 int count[255] T串在s中的字母出现的次数;
一个队列保存字母出现的顺序;
minValue保存最小的长度;
num 表示在i,j 之间的有效个数;
思路:滑动i,j直到num =s的长度,然后根据队列中的值去移动i,和更新count ,num ,minvalue