算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
## Minimum Window Substring


### 描述

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`.


### 分析

双指针,动态维护一个区间。尾指针不断往后扫,当扫到有一个窗口包含了所有`T`的字符后,然后再收缩头指针,直到不能再收缩为止。最后记录所有可能的情况中窗口最小的


### 代码

```cpp
// LeetCode, Minimum Window Substring
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
string minWindow(string S, string T) {
if (S.empty()) return "";
if (S.size() < T.size()) return "";

const int ASCII_MAX = 256;
int appeared_count[ASCII_MAX];
int expected_count[ASCII_MAX];
fill(appeared_count, appeared_count + ASCII_MAX, 0);
fill(expected_count, expected_count + ASCII_MAX, 0);

for (size_t i = 0; i < T.size(); i++) expected_count[T[i]]++;

int minWidth = INT_MAX, min_start = 0; // 窗口大小,起点
int wnd_start = 0;
int appeared = 0; // 完整包含了一个T
//尾指针不断往后扫
for (size_t wnd_end = 0; wnd_end < S.size(); wnd_end++) {
if (expected_count[S[wnd_end]] > 0) { // this char is a part of T
appeared_count[S[wnd_end]]++;
if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]])
appeared++;
}
if (appeared == T.size()) { // 完整包含了一个T
// 收缩头指针
while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]]
|| expected_count[S[wnd_start]] == 0) {
appeared_count[S[wnd_start]]--;
wnd_start++;
}
if (minWidth > (wnd_end - wnd_start + 1)) {
minWidth = wnd_end - wnd_start + 1;
min_start = wnd_start;
}
}
}

if (minWidth == INT_MAX) return "";
else return S.substr(min_start, minWidth);
}
};
```