# 76. Minimum Window Substring (Shortest Substring from Pangram)

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 empty string`""`.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Thoughts:

1. "Do" Section keeps tracking "head" and "len" variable by "len"'s value
2. Count: # character current sliding window needs (does not have)
3. Very similar to 438. Find All Anagrams in a String
``````class Solution {

public:
string minWindow(string s, string t) {
if(t.length() > s.length()) return "";
unordered_map <char, int> map;
for(int i = 0; i < t.length(); i++ ){
++map[t[i]];
}

int left = 0, right = 0, head = INT_MAX, len = INT_MAX, count = map.size();

while(right < s.length()){
char rightChar = s[right];
if(map.find(rightChar) != map.end()){
if(--map[rightChar] == 0) count --;
}
right ++;
while(count == 0){  // here we already find the window that contains the targeted substring
// do
if(right - left < len){
len = right - left;
}

// increment
char leftChar = s[left];
if (map.find(leftChar)!= map.end()){
if(++map[leftChar] > 0){
count++;
}
}
left ++;
}
}

if(len == INT_MAX) return "";
}
};
``````

Template: https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

Java Implementation: T: O(|S|), S:O(1)

``````class Solution {
public String minWindow(String s, String t) {
int [] map = new int [128];
char [] chs = s.toCharArray();
for(char c : t.toCharArray()){
map[c]++;
}

int count = t.length(), slow = 0, fast = 0, head = 0, len = Integer.MAX_VALUE;

while(fast < chs.length){
if(map[chs[fast++]]-- > 0) count--;
while(count == 0){
if(fast - slow < len) {
len = fast - slow;
}
if(map[chs[slow++]]++ == 0) count++;
}
}

return len == Integer.MAX_VALUE ? "": s.substring(head, head + len);
}
}
``````
``````string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto c: t) map[c]++;
int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
while(end<s.size()){
if(map[s[end++]]-->0) counter--; //in t
while(counter==0){ //valid
if(map[s[begin++]]++==0) counter++;  //make it invalid
}
}
return d==INT_MAX? "":s.substr(head, d);
}
``````
``````int findSubstring(string s){
vector<int> map(128,0);
int counter; // check whether the substring is valid
int begin=0, end=0; //two pointers, one point to tail and one  head
int d; //the length of substring

for() { /* initialize the hash map here */ }

while(end<s.size()){

if(map[s[end++]]-- ?){  /* modify counter here */ }

while(/* counter condition */){

/* update d here if finding minimum*/

//increase begin to make it invalid/valid again

if(map[s[begin++]]++ ?){ /*modify counter here*/ }
}

/* update d here if finding maximum*/
}
return d;
}
``````
``````def minWindow(self, s, t):
need, missing = collections.Counter(t), len(t)
i = I = J = 0
for j, c in enumerate(s, 1):
missing -= need[c] > 0
need[c] -= 1
if not missing:
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
if not J or j - i <= J - I:
I, J = i, j
return s[I:J]
``````
``````class Solution {
public:
string minWindow(string S, string T) {
if (S.empty() || T.empty())
{
return "";
}
int count = T.size();
int require[128] = {0};
bool chSet[128] = {false};
for (int i = 0; i < count; ++i)
{
require[T[i]]++;
chSet[T[i]] = true;
}
int i = -1;
int j = 0;
int minLen = INT_MAX;
int minIdx = 0;
while (i < (int)S.size() && j < (int)S.size())
{
if (count)
{
i++;
require[S[i]]--;
if (chSet[S[i]] && require[S[i]] >= 0)
{
count--;
}
}
else
{
if (minLen > i - j + 1)
{
minLen = i - j + 1;
minIdx = j;
}
require[S[j]]++;
if (chSet[S[j]] && require[S[j]] > 0)
{
count++;
}
j++;
}
}
if (minLen == INT_MAX)
{
return "";
}
return S.substr(minIdx, minLen);
}
};
``````