# 76. 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).

Example:

Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”

We use maps to maintain the frequency of the characters in T and S.
We also use two pointers to maintain a sliding window. Once the sliding window contains enough chars, we move the left ptrs forward and srhink the windows the the smallest possible.

``````class Solution {
public:
string minWindow(string s, string t) {
string result;
if (s.empty() || t.empty())
return result;

unordered_map<char, int> map;       //record freq
unordered_map<char, int> window;    //freq of letters in windows
int minLength = INT_MAX;
int fast = 0;
int slow = 0;
int currWindowLen = 0;
for(int i = 0; i < t.size(); i ++)
map[t[i]] ++;

for(unordered_map<char,int>::iterator it=map.begin(); it!=map.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';

for(; fast < s.size(); fast ++){
char c = s[fast];
if(map.find(c) != map.end()){ //if we this char in t
window ++;             //increase freq in windows
if(window <= map){
currWindowLen ++;       //if the just-seen letter can still be used to fill t
}
}

if(currWindowLen >= t.size()){ //we have found a window
//remove extra chars in the windows and move slow ptr forward
//1.we have too much char
//2.the slow is not even in the t.
while(map.find(s[slow]) == map.end() ||  window[s[slow]] > map[s[slow]]){
window[s[slow]] --;
slow ++;
}
if(fast - slow + 1 < minLength){
minLength = fast - slow + 1;
result = s.substr(slow, minLength);
}
}

}

return result;
}
};
``````
Posted on Categories Leetcode