Leetcode Minimum Window Substring Problem Solution

In this Leetcode Minimum Window Substring Problem Solution 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.

Problem solution in Python.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        freq = { }
        for i in t :
            freq[i] = freq[i] + 1 if i in freq.keys() else 1
        l = len(t) 
        r = len(s) 
        mid = 0 
        ans = ""
        while l <= r :
            mid = ( l + r ) >> 1 
            sl = self.solve( s , t ,  freq , mid )
            if sl != "":
                if len(ans) > len(sl) or ans == "" :
                    ans = sl 
                r = mid - 1 
            else:
                l = mid + 1 
        return ans 
    def solve(self , s ,  t , freq , mid ):
        freq_2 = {}
        ans = ""
        count = 0
        sz = len(t)
        for i in range( 0 , mid ):
            if s[i] in t :
                freq_2[s[i]] = freq_2[s[i]] + 1 if s[i] in  freq_2.keys() else 1 
                if freq_2[s[i]] <= freq[s[i]] : 
                    count = count + 1 
                    
        if count == sz : 
            return s[0:mid]
        
        l = 0 
        r = mid   
        
        while r < len(s):
            
            if s[l] in t :
                freq_2[s[l]] = freq_2[s[l]] - 1 
                if freq_2[s[l]] < freq[s[l]] : 
                    count = count - 1 
            l = l + 1 
            
            if s[r] in t :
                freq_2[s[r]] = freq_2[s[r]] + 1 if s[r] in freq_2.keys() else 1
                if freq_2[s[r]] <= freq[s[r]] : 
                    count = count + 1 
                    
            if count == sz :
                return s[l:r+1]
            r = r + 1 
        
                
        return ""

Problem solution in Java.

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> wc = IntStream.range(0, t.length()).mapToObj(i -> t.charAt(i)).collect(Collectors.toMap(k -> k, k -> 1, Integer::sum));
        int numCharSeen = 0;
        String minWindow = ""; int minLen = Integer.MAX_VALUE;
        for (int start = 0, end = 0; end < s.length(); end++) {
            // get end char, update cache
            char eChar = s.charAt(end);
            wc.computeIfPresent(eChar, (k, v) -> v - 1);
            if (wc.getOrDefault(eChar, -1) >= 0) numCharSeen++; // works both for invalid char and valid char
            // adjust start
            while (numCharSeen == t.length()) {
                // update result
                int curLen = end - start + 1;
                if (curLen < minLen) {
                    minLen = curLen;
                    minWindow = s.substring(start, end + 1);
                }
                // update cache
                char sChar = s.charAt(start);
                wc.computeIfPresent(sChar, (k, v) -> v + 1);
                if (wc.getOrDefault(sChar, -1) > 0) numCharSeen--; // works both for invalid char and valid char
                start++; // remember to update start here
            }
        } 
        return minWindow;
    }
}

Problem solution in C++.

string minWindow(string s, string t) {
        int left = 0, right = 0, min_len = INT_MAX, pos = -1;
        unordered_map<char, int> freq;
        for (char c : t) freq[c]++;
        int chars = freq.size();
        for (;right < s.size(); right++) {
            auto it = freq.find(s[right]);
            if (it != freq.end()) {
                it->second--;
                if (it->second == 0) chars--;
                while (chars == 0 && left <= right) {
                    if (right - left + 1 < min_len) {
                        min_len = right - left + 1;
                        pos = left;
                    }
                    
                    auto iit = freq.find(s[left]);
                    if (iit != freq.end()) {
                        iit->second++;
                        if (iit->second == 1) chars++;
                    }
                    left++;
                }
            }
        }
        if (pos == -1) return "";
        return s.substr(pos, min_len);
    }

Problem solution in C.

char* minWindow(char* s, char* t) {
    int left = 0;
    int right = 0;
    int resultL = 0;
    int resultR = 0;
    int i;
    int a[128] = {0};
    int b[128] = {0};
    for(i = 0; i < strlen(t); i++){
        a[*(t+i) - 0x0]++;
    }
    int window = INT_MAX;
    int temp = 0;
    for(right = 0; right < strlen(s); right++){
        if((a[*(s+right) - 0x0] != 0)){
            b[*(s+right) - 0x0]++;
            if(b[*(s+right) - 0x0] <= a[*(s+right) - 0x0]){
                temp++;
            }
        }
        if(temp >= strlen(t)){
            while((a[*(s+left) - 0x0] == 0) || (b[*(s+left) - 0x0] > a[*(s+left) - 0x0])){
                b[*(s+left) - 0x0]--;
                left++;
            }
            if((right - left) < window){
                window = right - left;
                resultL = left;
                resultR = right;
            }
            
            b[*(s+left) - 0x0]--;
            left++;
            temp--;
            
        }
    }
    if(window == INT_MAX) return "";
    char* result = (char*)malloc(sizeof(char)*(window+2));
    strncpy(result, s+resultL, window+1);
    result[window+1] = '\0';
    return result;
}