# 76. Minimum Window Substring(H)
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**.
A **substring** is a contiguous sequence of characters within the string.
**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?
### Solution:
\
就是说要在 `S`(source) 中找到包含 `T`(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的。
如果我们使用暴力解法，代码大概是这样的：
```java
for (int i = 0; i < s.size(); i++)
for (int j = i + 1; j < s.size(); j++)
if s[i:j] 包含 t 的所有字母:
更新答案
```
思路很直接，但是显然，这个算法的复杂度肯定大于 O(N^2) 了，不好。
**滑动窗口算法的思路是这样**：
1、我们在字符串 `S` 中使用双指针中的左右指针技巧，初始化 `left = right = 0`，把索引**左闭右开**区间 `[left, right)` 称为一个「窗口」。
2、我们先不断地增加 `right` 指针扩大窗口 `[left, right)`，直到窗口中的字符串符合要求（包含了 `T` 中的所有字符）。
3、此时，我们停止增加 `right`，转而不断增加 `left` 指针缩小窗口 `[left, right)`，直到窗口中的字符串不再符合要求（不包含 `T` 中的所有字符了）。同时，每次增加 `left`，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 `right` 到达字符串 `S` 的尽头。
这个思路其实也不难，**第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解**，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
下面画图理解一下，`needs` 和 `window` 相当于计数器，分别记录 `T` 中字符出现次数和「窗口」中的相应字符的出现次数。
初始状态：
[](https://labuladong.github.io/algo/images/slidingwindow/1.png)
增加 `right`，直到窗口 `[left, right]` 包含了 `T` 中所有字符：
[](https://labuladong.github.io/algo/images/slidingwindow/2.png)
现在开始增加 `left`，缩小窗口 `[left, right]`：
[](https://labuladong.github.io/algo/images/slidingwindow/3.png)
直到窗口中的字符串不再符合要求，`left` 不再继续移动：
[](https://labuladong.github.io/algo/images/slidingwindow/4.png)
之后重复上述过程，先移动 `right`，再移动 `left`…… 直到 `right` 指针到达字符串 `S` 的末端，算法结束。
如果你能够理解上述过程，恭喜，你已经完全掌握了滑动窗口算法思想。**现在我们来看看这个滑动窗口代码框架怎么用**：
首先，初始化 `window` 和 `need` 两个哈希表，记录窗口中的字符和需要凑齐的字符：
```cpp
unordered_map need, window;
for (char c : t) need[c]++;
```
然后，使用 `left` 和 `right` 变量初始化窗口的两端，不要忘了，区间 `[left, right)` 是左闭右开的，所以初始情况下窗口没有包含任何元素：
```cpp
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// 开始滑动
}
```
**其中 `valid` 变量表示窗口中满足 `need` 条件的字符个数**，如果 `valid` 和 `need.size` 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 `T`。
**现在开始套模板，只需要思考以下四个问题**：
1、当移动 `right` 扩大窗口，即加入字符时，应该更新哪些数据？
2、什么条件下，窗口应该暂停扩大，开始移动 `left` 缩小窗口？
3、当移动 `left` 缩小窗口，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
如果一个字符进入窗口，应该增加 `window` 计数器；如果一个字符将移出窗口的时候，应该减少 `window` 计数器；当 `valid` 满足 `need` 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。
下面是完整代码：
```cpp
string minWindow(string s, string t) {
unordered_map need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = INT_MAX;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 在这里更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// 返回最小覆盖子串
return len == INT_MAX ?
"" : s.substr(start, len);
}
JAVA Version:
class Solution {
public String minWindow(String s, String t)
{
Map needs = new HashMap<>();
for(char element: t.toCharArray())
{
needs.put(element, needs.getOrDefault(element, 0)+1);
}
Map windows = new HashMap<>();
int left = 0, right = 0, validLetterCount = 0;
int startIndex = 0, endIndex = 0, len = Integer.MAX_VALUE;
while (right < s.length())
{
char currentRight = s.charAt(right);
right++;
if(needs.containsKey(currentRight))
{
windows.put(currentRight, windows.getOrDefault(currentRight,0)+1);
if(needs.get(currentRight).equals(windows.get(currentRight)))
{
validLetterCount++;
}
}
while(validLetterCount == needs.size())
{
if(right-left < len)
{
startIndex = left;
endIndex = right;
len = right -left;
}
char currentLeft = s.charAt(left);
left++;
if(needs.containsKey(currentLeft))
{
if(needs.get(currentLeft).equals(windows.get(currentLeft)))
{
validLetterCount--;
}
windows.put(currentLeft, windows.get(currentLeft)-1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(startIndex, endIndex);
}
}
```
> PS：使用 Java 的读者要尤其警惕语言特性的陷阱。Java 的 Integer，String 等类型判定相等应该用 `equals` 方法而不能直接用等号 `==`，这是 Java包装类的一个隐晦细节。所以在左移窗口更新数据的时候，不能直接改写为 `window.get(d) == need.get(d)`，而要用 `window.get(d).equals(need.get(d))`，之后的题目代码同理。
需要注意的是，当我们发现某个字符在 `window` 的数量满足了 `need` 的需要，就要更新 `valid`，表示有一个字符已经满足要求。而且，你能发现，两次对窗口内数据的更新操作是完全对称的。
当 `valid == need.size()` 时，说明 `T` 中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。
移动 `left` 收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。
至此，应该可以完全理解这套框架了，滑动窗口算法又不难，就是细节问题让人烦得很。**以后遇到滑动窗口算法，你就按照这框架写代码，保准没有 bug，还省事儿**。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://junnie.gitbook.io/nine-chapter/6.array/76.-minimum-window-substring-h.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.