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.

Minimum Window Substring Problem Solution

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;
}

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment