76. Minimum Window Substring - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_map = collections.defaultdict(int)
        for ch in t:
            t_map[ch] += 1
        
        left = 0
        res = ''
        window = collections.defaultdict(int)
        completed_unique = 0
        for right, ch in enumerate(s):
            if ch in t_map:
                window[ch] += 1
                if window[ch] == t_map[ch]:
                    completed_unique += 1
            if completed_unique == len(t_map):
                while left < right and (s[left] not in t_map or window[s[left]] > t_map[s[left]]):
                    if s[left] in t_map:
                        window[s[left]] -= 1
                    left += 1
                if not res or len(res) > right - left + 1:
                    res = s[left:right+1]
        return res     

S = "ADOBECODEBANC"
T = "ABC"

step1: "ADOBEC" -> "ADOBEC" //first window that contain all chars in T
step2: "ADOBECODEB" -> "ADOBECODEB"
step3: "ADOBECODEBA" -> "BECODEBA"
step4: "CODEBANC" -> "BANC"

                if (inWindow[c] <= inTarget[c]) { 
                    len--;
                    if (len == 0)   
                        found = true;
                }

string minWindow(string s, string t) {
        vector<int> inTarget(256);
        int num = 0; //# of different chars
        for (int i = 0; i < t.length(); i++) {
            char c = t[i];
            if (inTarget[c] == 0)    num++;
            inTarget[c]++;
        }
        
        string res;
        vector<int> inWin(256);
        for (int left = 0, right = 0; right < s.length(); right++) {
            char r = s[right];
            if (inTarget[r] == 0)   continue;
            inWin[r]++;
            if (num != 0 && inWin[r] == inTarget[r])    num--;
            if (num == 0) {
                while (left <= right) {
                    char l = s[left];
                    if (inTarget[l] == 0) {
                        left++;
                    } else if (inWin[l] > inTarget[l]) {
                        left++;
                        inWin[l]--;
                    } else {
                        break;
                    }
                }
                if (res.empty() || res.length() > right - left + 1) {
                    res = s.substr(left, right - left + 1);
                }
            }
        }
        return res;
    }