Problem
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
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
var map = {};
var sLen = s.length;
var tLen = t.length;
var count = tLen;
var min = Number.MAX_SAFE_INTEGER;
var head = 0;
var left = 0;
var right = 0;
if (!sLen || !tLen) return '';
for (var i = 0; i < tLen; i++) {
if (map[t[i]] === undefined) {
map[t[i]] = 1
} else {
map[t[i]]++;
}
}
while (right < sLen) {
if (map[s[right]] !== undefined) {
if (map[s[right]] > 0) count--;
map[s[right]]--;
}
right++;
while (count === 0) {
if (right - left < min) {
min = right - left;
head = left;
}
if (map[s[left]] !== undefined) {
if (map[s[left]] === 0) count++;
map[s[left]]++;
}
left++;
}
}
return min === Number.MAX_SAFE_INTEGER ? '' : s.substr(head, min);
};
Explain:
see Here is a 10-line template that can solve most 'substring' problems.
用哈希表保存各字符的数量,双指针表示当前窗口,用计数器来判断是否符合条件。符合条件后,记录窗口位置、最小值;更新双指针、计数器。
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).