# 76. Minimum Window Substring

Given two strings `s` and `t` of lengths `m` and `n` respectively, return the minimum window substring of`s` such that every character in`t` (including duplicates) is included in the window. If there is no such substring, return the empty string`""`.

The testcases will be generated such that the answer is unique.

Example 1:

``````Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
``````

Example 2:

``````Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
``````

Example 3:

``````Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
``````

Constraints:

• `m == s.length`
• `n == t.length`
• `1 <= m, n <= 105`
• `s` and `t` consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in `O(m + n)` time?

- 先扫描一遍T，把对应的字符及其出现的次数存到 HashMap 中。

- 然后开始遍历S，就把遍历到的字母对应的 HashMap 中的 value 减一，如果减1后仍大于等于0，cnt 自增1。

- 如果 cnt 等于T串长度时，开始循环，纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移，如果某个移除掉的字母是T串中不可缺少的字母，那么 cnt 自减1，表示此时T串并没有完全匹配。

``````// Memory Limit Exceeded
class Solution {
public:
string minWindow(string s, string t) {
string res;
unordered_map<char, int> letterCnt;
int left = 0, cnt = 0, minLen = INT_MAX;
for (char c : t) ++letterCnt[c];
for (int i = 0; i < s.size(); ++i) {
if (--letterCnt[s[i]] >= 0) ++cnt;
while (cnt == t.size()) {
if (minLen > i - left + 1) {
minLen = i - left + 1;
res = s.substr(left, minLen);
}
if (++letterCnt[s[left]] > 0) --cnt;
++left;
}
}
return res;
}
};
``````

``````class Solution {
public:
string minWindow(string s, string t) {
vector<int> letterCnt(128);
int left = 0, cnt = 0, minLeft = -1, minLen = INT_MAX;
for (char c : t) ++letterCnt[c];
for (int i = 0; i < s.size(); ++i) {
if (--letterCnt[s[i]] >= 0) ++cnt;
while (cnt == t.size()) {
if (minLen > i - left + 1) {
minLen = i - left + 1;
minLeft = left;
}
if (++letterCnt[s[left]] > 0) --cnt;
++left;
}
}
return minLeft == -1 ? "" : s.substr(minLeft, minLen);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/76

Substring with Concatenation of All Words

Minimum Size Subarray Sum

Sliding Window Maximum

Permutation in String

Smallest Range

Minimum Window Subsequence

https://leetcode.com/problems/minimum-window-substring/

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation