# Leetcode-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.

## AC代码

``````#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <limits.h>
#include <string.h>
#include <cstdio>
#include <cstdlib>

using namespace std;

bool is_all_non_neg(const vector<int> &v)
{
for (int i=0; i<v.size(); ++i)
if (v[i]<0)
return false;
return true;
}

string minWindow(string S, string T) {
if (S.size()==0 || T.size()==0) return "";
int slow=0, fast=0;

vector<bool> is_in_T(256,false);
for (int i=0; i<T.size(); ++i)  is_in_T[T[i]]=true;

vector<int> dist(256, 0);
for (int i=0; i<T.size(); ++i)  dist[T[i]]--;
if (is_in_T[S[0]]) dist[S[0]]++;

string min_w;   // the minimum window found so far
int min_w_size = INT_MAX;   // the size of the minimum window
bool have_found = false;    // if a window has been found
while (slow<S.size() && fast<S.size()) {
if (!is_in_T[S[slow]]) {
++slow;
continue;
}
if (dist[S[slow]]>0) {
--dist[S[slow]];
++slow;
} else {
if (!have_found)
have_found = is_all_non_neg(dist);
if (have_found && min_w_size>fast-slow+1) { // once we have found a window, the window is always good.
min_w_size = fast-slow+1;
min_w = S.substr(slow, min_w_size);
}
++fast;     // the window must be extended given slow cannot move
if (fast<S.size() && is_in_T[S[fast]]) ++dist[S[fast]];
}

}
return min_w;
}

int main()
{
string s, t;
while(cin>>s>>t)
cout<<minWindow(s, t)<<endl;
return 0;
}
``````