sundeepblue
3/21/2014 - 9:21 PM

## Finding the Minimum Window in S which Contains All Elements from T. Given a set T of characters and a string S, find the minimum window in S

Finding the Minimum Window in S which Contains All Elements from T. Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n). eg, S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”.

``````#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;
string find_minimum_window(string s, string t) {
if(s.empty() || t.empty()) return;

int ns = s.size(), nt = t.size();
vector<int> total(256, 0);
vector<int> sofar(256, 0);
for(int i=0; i<nt; i++)
total[t[i]]++;

int L = 0, R;
int minL = 0;                           //gist2
int count = 0;
int min_win_len = INT_MAX;

for(R=0; R<ns; R++) {                   // gist0, a big for loop
if(total[s[R]] == 0) continue;
else sofar[s[R]]++;

if(sofar[s[R]] <= total[s[R]])      // gist1, <= not <
count++;

if(count == nt) {                   // POS1
while(true) {
char c = s[L];
if(total[c] == 0) { L++; }
else if(sofar[c] > total[c]) {
sofar[c]--;
L++;
}
else break;
}
if(R - L + 1 < min_win_len) {   // this judge should be inside POS1
min_win_len = R - L + 1;
minL = L;
}
}
}
string res;
if(count == nt)                         // gist3, cannot forget this.
res = s.substr(minL, min_win_len);  // gist4, start from "minL" not "L"
return res;
}
int main() {
string s = "abdccdedca";
cout << find_minimum_window(s, "acd");
}``````