# Minimum Window Substring Problem Solution

Minimum Window Substring Problem: Given two strings `s` and `t` of lengths `m` and `n` respectively, return the minimum window substring of `s` such that every character in `t` (including duplicates) is included in the window. If there is no such substring, return the empty string `""`.

The testcases will be generated such that the answer is unique.

substring is a contiguous sequence of characters within the string.

Example :

```Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.```

## Problem Solution In Python

``````class Solution:
def minWindow(self, s: str, t: str) -> str:
len_s, len_t = len(s), len(t)
if not s or not t or len_s<len_t:
return ""

dic, count = {}, 0
left, right, min_width = 0, 0, len_s + 1
res = ""
for c in t:
dic[c] = dic.get(c,0)+1

while right < len_s:
if s[right] in dic:
if dic[s[right]]>0:
count+=1
dic[s[right]]-=1

while count == len(t):
if right-left+1 < min_width:
min_width = right-left+1
res = s[left:right+1]

if s[left] in dic:
dic[s[left]]+=1
if dic[s[left]] > 0:
count-=1
left+=1
right+=1
return res
``````

## Problem Solution In Java

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

int tLen = t.length();
int count = 0;
int start = 0, len = s.length() + 1;
for (int right = 0, left = 0; right < s.length(); right++) {
if (cnt[chs[right]]-- > 0) {
count++;
}
while (left < right && cnt[chs[left]] < 0) {
if (++cnt[chs[left++]] > 0)
count--;
}
if (count == tLen && right - left + 1 < len) {
start = left;
len = right - left + 1;
}
}
return len == s.length() + 1 ? "" : s.substring(start, start + len);
}
}
``````

## Problem Solution In C++

``````class Solution {
public:
string minWindow(string s, string t) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
pair<int,int> ans = {-1,-1};
int len = 1e7;
int n = s.length();

unordered_map <int,int> m1,curr;
for(char c : t){
m1[c]++;
}

int i = 0 ;
int cnt = t.size();
for(int j= 0 ;j<n;j++){
curr[s[j]]++;
if(m1.find(s[j])!=m1.end()){
if(curr[s[j]] <= m1[s[j]]){
cnt--;
}
}
while(curr[s[i]]>m1[s[i]]){
curr[s[i]]--;
i++;
}
if(cnt>0)continue;
if(j-i+1 < len ){
len = j-i+1;
ans = {i,j};
}
}
if(ans == make_pair(-1,-1)){
return "";
}else{
return s.substr(ans.first,ans.second-ans.first+1);
}
}
};
``````

## Problem Solution In C

``````char* minWindow(char* s, char* t) {
int scnt[256]={0},tcnt[256]={0},reti=0,retj=INT_MAX,i=0,j=0,uni = 0,ucnt = 0;
const int slen = strlen(s);
for(char * x = t;  *x; x++)
if(++tcnt[*x] == 1)
uni++;
while(ucnt < uni && j < slen)
if(++scnt[s[j]]==tcnt[s[j++]])
ucnt++;
if(ucnt == uni)
while(j <= slen)
{
while(scnt[s[i]] > tcnt[s[i]])
scnt[s[i++]] --;
if(j-i < retj - reti)
reti= i,retj=j;
scnt[s[j++]]++;
}
if(retj == INT_MAX)
return s+slen;
s[retj]=0;
return s+reti;
}``````