Leetcode Minimum Window Substring problem solution

In this Leetcode Minimum Window Substring problem solution, we have 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 “”.

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

coding problems solutions