# 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"
Note:
- If there is no such window in S that covers all characters in T, return the empty string "".
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
# Solution
Approach 1: Sliding Window.
# Code (Python)
Approach 1:
import collections
class Solution:
def minWindow(self, s: str, t: str) -> str:
needed = collections.Counter(t)
letters_missing = len(needed)
min_substring = s + s
l = 0
for r in range(len(s)):
if s[r] in needed:
needed[s[r]] -= 1
if needed[s[r]] == 0:
letters_missing -= 1
if letters_missing > 0:
continue
while l < r and (s[l] not in needed or needed[s[l]] < 0):
if s[l] in needed:
needed[s[l]] += 1
l += 1
if r - l + 1 < len(min_substring):
min_substring = s[l:r+1]
return min_substring if len(min_substring) <= len(s) else ""
# Code (C++)
Approach 1:
// Sliding Window.
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char,int> umap;
for (int i = 0; i < t.size(); ++i)
{
umap[t[i]]++;
}
int head = 0;
int tail = 0;
int count = t.size();
int minResLen = s.size() + 1;
string res = "";
while (count == 0 || tail < s.size())
{
if (count == 0)
{
if (umap.find(s[head]) != umap.end())
{
if (umap[s[head]] == 0)
{
count++;
if (tail - head < minResLen)
{
minResLen = tail - head;
res = s.substr(head, minResLen);
}
}
umap[s[head]]++;
}
head++;
}
else
{
if (umap.find(s[tail]) != umap.end())
{
if (umap[s[tail]] > 0)
count--;
umap[s[tail]]--;
}
tail++;
}
}
return res;
}
};
// Optimized Sliding Window.
// This kind of scenario might happen when length of string T is way too small than the length of string S and string S consists of numerous characters which are not present in T.
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char,int> umap;
for (int i = 0; i < t.size(); ++i)
{
umap[t[i]]++;
}
vector<pair<char,int>> filteredS;
for (int i = 0; i < s.size(); ++i)
{
if (umap.find(s[i]) != umap.end())
filteredS.push_back(make_pair(s[i], i));
}
int head = 0;
int tail = 0;
int count = t.size();
int minResLen = s.size() + 1;
string res = "";
while (count == 0 || tail < filteredS.size())
{
if (count == 0)
{
if (umap[filteredS[head].first] == 0)
{
count++;
int len = filteredS[tail-1].second - filteredS[head].second + 1;
if (len < minResLen)
{
minResLen = len;
res = s.substr(filteredS[head].second, minResLen);
}
}
umap[filteredS[head].first]++;
head++;
}
else
{
if (umap[filteredS[tail].first] > 0)
count--;
umap[filteredS[tail].first]--;
tail++;
}
}
return res;
}
};