【Day 46 】2022-12-16 - 76. 最小覆盖子串

[azl397985856]

76. 最小覆盖子串

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/minimum-window-substring

前置知识

• Sliding Window
• 哈希表

  题目描述

  
  给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入：S = "ADOBECODEBANC", T = "ABC" 输出："BANC"

提示：

如果 S 中不存这样的子串，则返回空字符串 ""。 如果 S 中存在这样的子串，我们保证它是唯一的答案。

[Elon-Lau]

class Solution { public: unordered_map <char, int> ori, cnt;

bool check() {
    for (const auto &p: ori) {
        if (cnt[p.first] < p.second) {
            return false;
        }
    }
    return true;
}

string minWindow(string s, string t) {
    for (const auto &c: t) {
        ++ori[c];
    }

    int l = 0, r = -1;
    int len = INT_MAX, ansL = -1, ansR = -1;

    while (r < int(s.size())) {
        if (ori.find(s[++r]) != ori.end()) {
            ++cnt[s[r]];
        }
        while (check() && l <= r) {
            if (r - l + 1 < len) {
                len = r - l + 1;
                ansL = l;
            }
            if (ori.find(s[l]) != ori.end()) {
                --cnt[s[l]];
            }
            ++l;
        }
    }

    return ansL == -1 ? string() : s.substr(ansL, len);
}

};

[bwspsu]

(Referring to the solution)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l, counter, N, ct = 0, Counter(), len(s), Counter(t)
        k = 0
        ret, ans = inf, ""
        for r in range(N):
            counter[s[r]] += 1
            if s[r] in t and counter[s[r]] == ct[s[r]]:
                k += 1
            while k == len(ct):
                if r - l + 1 < ret:
                    ans = s[l:r+1]
                ret = min(r - l + 1, ret)
                counter[s[l]] -= 1
                if s[l] in t and counter[s[l]] == ct[s[l]]-1:
                    k -= 1
                l += 1
        return ans

[Ryanbaiyansong]

class Solution: def minWindow(self, s: str, t: str) -> str: need = Counter(t) valid = j = 0 res = "" minLen = inf window = defaultdict(int) n = len(s) for i,ch in enumerate(s): if ch in need: window[ch] += 1 if window[ch] == need[ch]: valid += 1

        while j<n and valid==len(need):
            sz = i-j+1
            if sz < minLen:
                minLen = sz
                res = s[j:j+minLen]
            if s[j] in need:
                if window[s[j]] == need[s[j]]:
                    valid -= 1
                window[s[j]] -= 1
            j += 1

    return res

[heng518]

class Solution { public: string minWindow(string s, string t) { unordered_map<char, int> need, window;

    for(char c : t)
        need[c]++;

    int left = 0, right = 0, valid = 0;
    int start = 0, len = INT_MAX;

    while(right < s.size())
    {
        char c = s[right];
        right++;

        if(need.count(c))
        {
            window[c]++;
            if(window[c] == need[c])
                valid++;
        }

        while(valid == need.size())
        {
            if(right - left < len)
            {
                start = left;
                len = right - left;
            }

            char c = s[left];

            if(need.count(c))
            {
                if(window[c] == need[c])
                    valid--;
                window[c]--;
            }
            left++;
        }
    }

    return len == INT_MAX ? "" : s.substr(start, len);
}

};

[snmyj]

lass Solution:
    def minWindow(self, s: 'str', t: 'str') -> 'str':
        from collections import Counter
        t = Counter(t)
        lookup = Counter()
        start = 0
        end = 0
        min_len = float("inf")
        res = ""
        while end < len(s):
            lookup[s[end]] += 1
            end += 1
            #print(start, end)
            while all(map(lambda x: lookup[x] >= t[x], t.keys())):
                if end - start < min_len:
                    res = s[start:end]
                    min_len = end - start
                lookup[s[start]] -= 1
                start += 1
        return res

[zrtch]

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let l = 0
    let r = 0
    const need = new Map()
    for(let c of t){
        need.set( c,need.has(c) ? need.get(c) + 1 : 1)
    }

    let needType = need.size
    let res = ''
    while(r<s.length){
        let c = s[r]
        if(need.has(c)){
            need.set( c,need.get(c) -1 )
            if( need.get(c) === 0) needType -= 1
        }

        while(needType === 0){
            const newRes = s.substring(l,r+1)
            if( !res || newRes.length < res.length ) res = newRes

            const c2 = s[l]
            if(need.has(c2)){
                need.set(c2,need.get(c2) + 1)
                if( need.get(c2) === 1 ) needType += 1
            }
            l += 1
        }
        r += 1
    }
    return res
};

[zrtch]

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let l = 0
    let r = 0
    const need = new Map()
    for(let c of t){
        need.set( c,need.has(c) ? need.get(c) + 1 : 1)
    }

    let needType = need.size
    let res = ''
    while(r<s.length){
        let c = s[r]
        if(need.has(c)){
            need.set( c,need.get(c) -1 )
            if( need.get(c) === 0) needType -= 1
        }

        while(needType === 0){
            const newRes = s.substring(l,r+1)
            if( !res || newRes.length < res.length ) res = newRes

            const c2 = s[l]
            if(need.has(c2)){
                need.set(c2,need.get(c2) + 1)
                if( need.get(c2) === 1 ) needType += 1
            }
            l += 1
        }
        r += 1
    }
    return res
};

[zrtch]

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let l = 0
    let r = 0
    const need = new Map()
    for(let c of t){
        need.set( c,need.has(c) ? need.get(c) + 1 : 1)
    }

    let needType = need.size
    let res = ''
    while(r<s.length){
        let c = s[r]
        if(need.has(c)){
            need.set( c,need.get(c) -1 )
            if( need.get(c) === 0) needType -= 1
        }

        while(needType === 0){
            const newRes = s.substring(l,r+1)
            if( !res || newRes.length < res.length ) res = newRes

            const c2 = s[l]
            if(need.has(c2)){
                need.set(c2,need.get(c2) + 1)
                if( need.get(c2) === 1 ) needType += 1
            }
            l += 1
        }
        r += 1
    }
    return res
};

[testplm]

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need = collections.Counter(t)            #hash table to store char frequency
        missing = len(t)                         #total number of chars we care
        start, end = 0, 0
        i = 0
        for j, char in enumerate(s, 1):          #index j from 1
            if need[char] > 0:
                missing -= 1
            need[char] -= 1
            if missing == 0:                     #match all chars
                while i < j and need[s[i]] < 0:  #remove chars to find the real start
                    need[s[i]] += 1
                    i += 1
                need[s[i]] += 1                  #make sure the first appearing char satisfies need[char]>0
                missing += 1                     #we missed this first char, so add missing by 1
                if end == 0 or j-i < end-start:  #update window
                    start, end = i, j
                i += 1                           #update i to start+1 for next window
        return s[start:end]

• Time:O(n)
• Space:O(1)

[Alyenor]

function minWindow(s: string, t: string): string {
  if (s.length < t.length) return ''
  if(s===t) return s
  const ht = new Map<string, number>()
  const hs = new Map<string, number>()

  t.split('').forEach(c => ht.set(c, 1 + (ht.get(c) ?? 0)))

  let res = ''
  let cnt = 0
  const sArr = s.split('')
  for (let i = 0, j = 0; i < sArr.length; i++) {
    const c = sArr[i]
    hs.set(c, 1 + (hs.get(c) ?? 0))
    if (!ht.has(c)) continue

    if (ht.get(c)! >= hs?.get(c)!) {
      cnt++
    }

    while (!ht.has(sArr[j]) || hs.get(sArr[j])! > ht.get(sArr[j])!) {
      hs.set(sArr[j], hs.get(sArr[j])! - 1)
      j++
    }

    if (cnt >= t.length) {
      if (res === '' || res.length > i - j + 1) {
        res = sArr.slice(j, i + 1).join('')
      }
    }
  }

  return res

};

[JancerWu]

滑动窗口+字母哈希

[xuanaxuan]

const minWindow = (s, t) => {
  let minLen = s.length + 1;
  let start = s.length;     // 结果子串的起始位置
  let map = {};             // 存储目标字符和对应的缺失个数
  let missingType = 0;      // 当前缺失的字符种类数
  for (const c of t) {      // t为baac的话，map为{a:2,b:1,c:1}
    if (!map[c]) {
      missingType++;        // 需要找齐的种类数 +1
      map[c] = 1;
    } else {
      map[c]++;
    }
  }
  let l = 0, r = 0;                // 左右指针
  for (; r < s.length; r++) {      // 主旋律扩张窗口，超出s串就结束
    let rightChar = s[r];          // 获取right指向的新字符
    if (map[rightChar] !== undefined) map[rightChar]--; // 是目标字符，它的缺失个数-1
    if (map[rightChar] == 0) missingType--;   // 它的缺失个数新变为0，缺失的种类数就-1
    while (missingType == 0) {                // 当前窗口包含所有字符的前提下，尽量收缩窗口
      if (r - l + 1 < minLen) {    // 窗口宽度如果比minLen小，就更新minLen
        minLen = r - l + 1;
        start = l;                 // 更新最小窗口的起点
      }
      let leftChar = s[l];          // 左指针要右移，左指针指向的字符要被丢弃
      if (map[leftChar] !== undefined) map[leftChar]++; // 被舍弃的是目标字符，缺失个数+1
      if (map[leftChar] > 0) missingType++;      // 如果缺失个数新变为>0，缺失的种类+1
      l++;                          // 左指针要右移 收缩窗口
    }
  }
  if (start == s.length) return "";
  return s.substring(start, start + minLen); // 根据起点和minLen截取子串
};

[mayloveless]

思路

字母计数，用滑动窗口遍历字符串，只要符合条件字母，则进入窗口，一直到收集完全，记录收尾并记录最小值。之后收缩左边界，继续遍历。

代码

var minWindow = function(s, t) {
    if(t.length>s.length)return '';
    const needs = {};
    for(let i=0;i<t.length;i++){ // t的map
        if(needs[t[i]]) {
            needs[t[i]] += 1;
        }else {
            needs[t[i]] = 1;
        }
    }

    let count = 0;
    let left = 0;
    let min = Infinity;
    let head = 0;
    let end = s.length-1;
    for(let right = 0;right<s.length;right++){
        if(needs[s[right]] !== undefined){
            if (needs[s[right]]>0) {
                count++;
            }
            needs[s[right]]--;
        }
        while(count === t.length){
            if(right-left<min){
                min = right-left;
                head = left;
                end = right;
            }
            if(needs[s[left]]!== undefined){    /* 收缩左边界 */
                if( needs[s[left]]>=0){
                    count--;
                }
                needs[s[left]]++;
            }
            left++;
        }
    }

    if(min === Infinity) return '';
    return s.substr(head,end-head+1)

};

复杂度

时间：O(n+m)，s和t的长度 空间：O(C) t字符集大小

[chenming-cao]

解题思路

滑动窗口+哈希表。用哈希表储存字符串t中字符出现频率信息。然后用变量match记录已经子串中已经对应上的字符数量。如果match == t.length()则说明t中字符已经被全部对应，符合条件的子字符串已经找到。寻找字符串时候用可变大小滑动窗口。定义左右指针，起始点为0。然后先移动右指针扩大窗口，找到t中对应字符则哈希表中字符数量减1，字符数量不小于0的同时match加1，如此循环直到右指针越界。当窗口内的子字符串符合条件时，开始移动左指针缩小窗口，如果当前字符在t中出现，则哈希表中字符数量加1，字符数量大于0的同时match减1，如此循环直到窗口内的子字符串无法符合条件。

代码

class Solution {
    public String minWindow(String s, String t) {
        int slen = s.length();
        int tlen = t.length();

        if (slen < tlen) return "";
        String res = "";
        Map<Character, Integer> map = new HashMap<>();
        // calculate the frequency of each character in t
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int min = slen + 1, match = 0; // use match to check whether substring in s contains all the characters in t
        int l = 0, r = 0;
        while (r < slen) {
            // move r to find characters until match == tlen
            char c = s.charAt(r);
            if (map.containsKey(c)) {
                int val = map.get(c) - 1;
                if (val >= 0) match++;
                map.put(c, val);
            }

            while (match == tlen) {
                // record possible result, if the length of substring is smaller than current min
                if (r - l + 1 < min) {
                    min = r - l + 1;
                    res = s.substring(l, r + 1);
                }
                // move l to decrease the size of the substring
                char d = s.charAt(l);
                if (map.containsKey(d)) {
                    int val = map.get(d) + 1;
                    if (val > 0) match--; // if val > 0, then one of this character is missing, we will need to find it in the later part of the string
                    map.put(d, val);
                }
                l++;
            }
            r++;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(N + K)，N为字符串s长度，K为字符串t长度
• 空间复杂度：O(S)，S为哈希表大小

[RestlessBreeze]

思路

滑动窗口

代码

class Solution {
public:
    unordered_map <char, int> ori, cnt;

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }

        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

[FlipN9]

class Solution {
    public String minWindow(String s, String t) {        
        if (s.length() < t.length()) return "";

        int minStart = 0;
        int minLen = Integer.MAX_VALUE;

        int required = t.length();               
        int[] count = new int['z' - 'A' + 1];             

        for (char c : t.toCharArray())
            count[c - 'A']++; 

        int l = 0, r = 0;

        while (r < s.length()) { 
            if (--count[s.charAt(r++) - 'A'] >= 0)
                required--;
            while (required == 0) {
                if (minLen > r - l) {
                    minLen = r - l;
                    minStart = l;
                }
                if (count[s.charAt(l++) - 'A']++ >= 0)
                    required++;
            }
        }
        return minLen == Integer.MAX_VALUE? "" : s.substring(minStart, minStart + minLen);
    }
}

[buer1121]

class Solution: def minWindow(self, s: str, t: str) -> str:

思路是滑动窗口：

    ###代码：
    if s==t:
        return s
    n1,need=len(s), len(t)
    if n1<need:
        return ""

    cnt=collections.Counter(t)

    start,end=0,-1
    min_len=n1+1
    left,right=0,0

    for right in range(n1):
        ch =s[right]
        if ch in cnt:
            if cnt[ch]>0:
                need-=1
            cnt[ch]-=1

        while need==0:
            if right-left+1<min_len:    #出现了更短的子串
                min_len=right-left+1
                start,end=left,right

            ch=s[left]
            if ch in cnt:
                if cnt[ch]>=0:
                    need+=1
                cnt[ch]+=1
            left+=1

    return s[start:end+1]

[Abby-xu]

class Solution: def minWindow(self, s: str, t: str) -> str: from collections import Counter

    temp = Counter(t)
    count = len(temp)

    i, j = 0, 0
    string = ""
    mini = 10 ** 6

    while j < len(s):           
        if s[j] in temp:
            temp[s[j]] -= 1
            if temp[s[j]] == 0:
                count -= 1

        while count == 0 and i <= j:

            if (j - i + 1) < mini:
                mini = (j - i + 1)
                string = s[i: j + 1]

            if s[i] in temp:
                temp[s[i]] += 1
                if temp[s[i]] == 1:
                    count += 1

            i += 1        
        j += 1               
    return string

[tiandao043]

思路

滑动窗口

代码

class Solution {
public:
    string minWindow(string s, string t) {
        if(s.length()<t.length())return "";
        string ans;
        int n=INT_MAX;
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
        // cout<<need.size()<<endl;

        int left = 0, right = 0;
        int valid = 0; 
        int cnt=t.size();
        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right];
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    valid++;
                }
            }

            /*** debug 输出的位置 ***/
            printf("window: [%d, %d) %d \n", left, right,valid);
            /********************/

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // cout<<(right-left)<<endl;
                    if(n>(right-left)){                        
                        ans=s.substr(left,right-left);
                        n=right-left;
                    }

                // d 是将移出窗口的字符
                char d = s[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if(need.count(d)){                    
                    if(window[d]==need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }

        }
        return ans;
    }
};

O(N+K) O(C)

[bookyue]

code

    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";

        int[] cnt = new int[128];
        for (int i = 0; i < t.length(); i++)
            cnt[t.charAt(i)]++;

        int need = t.length();
        int size = s.length() + 1;
        int start = 0;
        int l = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if (cnt[c] > 0) need--;

            cnt[c]--; // push in

            if (need != 0) continue;

            while (l < r && cnt[s.charAt(l)] < 0) {
                cnt[s.charAt(l)]++; // pull out
                l++;
            }

            if (r - l + 1 < size) {
                size = r - l + 1;
                start = l;
            }

            cnt[s.charAt(l)]++;
            l++;
            need++;
        }

        return size != s.length() + 1 ? s.substring(start, start + size) : "";
    }

[A-pricity]

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let l = 0
    let r = 0
    const need = new Map()
    for(let c of t){
        need.set( c,need.has(c) ? need.get(c) + 1 : 1)
    }

    let needType = need.size
    let res = ''
    while(r<s.length){
        let c = s[r]
        if(need.has(c)){
            need.set( c,need.get(c) -1 )
            if( need.get(c) === 0) needType -= 1
        }

        while(needType === 0){
            const newRes = s.substring(l,r+1)
            if( !res || newRes.length < res.length ) res = newRes

            const c2 = s[l]
            if(need.has(c2)){
                need.set(c2,need.get(c2) + 1)
                if( need.get(c2) === 1 ) needType += 1
            }
            l += 1
        }
        r += 1
    }
    return res
};

[wtdcai]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
            need=collections.defaultdict(int)
            for c in t:
                need[c]+=1
            needCnt=len(t)
            i=0
            res=(0,float('inf'))
            for j,c in enumerate(s):
                if need[c]>0:
                    needCnt-=1
                need[c]-=1
                if needCnt==0:       
                    while True:      
                        c=s[i] 
                        if need[c]==0:
                            break
                        need[c]+=1
                        i+=1
                    if j-i<res[1]-res[0]:   
                        res=(i,j)
                    need[s[i]]+=1  
                    needCnt+=1
                    i+=1
            return '' if res[1]>len(s) else s[res[0]:res[1]+1]

[paopaohua]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
            need=collections.defaultdict(int)
            for c in t:
                need[c]+=1
            needCnt=len(t)
            i=0
            res=(0,float('inf'))
            for j,c in enumerate(s):
                if need[c]>0:
                    needCnt-=1
                need[c]-=1
                if needCnt==0:       
                    while True:      
                        c=s[i] 
                        if need[c]==0:
                            break
                        need[c]+=1
                        i+=1
                    if j-i<res[1]-res[0]:   
                        res=(i,j)
                    need[s[i]]+=1  
                    needCnt+=1
                    i+=1
            return '' if res[1]>len(s) else s[res[0]:res[1]+1]

[klspta]

class Solution {
    public String minWindow(String s, String t) {
        char[] str = s.toCharArray();
        char[] ts = t.toCharArray();

        int[] map = new int[256];

        for(char c : ts){
            map[c]++;
        }
        int right = 0;
        int left = 0; 
        int ansL = -1;
        int ansR = -1;
        int minLen = Integer.MAX_VALUE;
        int all = ts.length;
        while(right != str.length){
            map[str[right]]--;
            if(map[str[right]] >= 0){
                all--;
            }
            if(all == 0){
                while(map[str[left]] < 0){
                    map[str[left++]]++;
                }
                if(minLen > right - left + 1){
                    minLen = right - left + 1;
                    ansL = left;
                    ansR = right;
                }
            }
            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(ansL, ansR + 1);

    }
}

[BruceZhang-utf-8]

思路

• 滑动窗口+哈希表

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    // 通过滑动窗口来解决
    Map<Character, Integer> osiMap = new HashMap<>(); // 存储字符串t中每个字符和每个字符出现的次数
    Map<Character, Integer> cntMap = new HashMap<>(); // 动态存储截取的字符串中每个字符包含的个数

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char a = t.charAt(i);
            osiMap.put(a, osiMap.getOrDefault(a, 0) + 1);
        }
        int sLen = s.length();
        int l = 0, r = -1;
        int ansL = -1, ansR = -1, len = Integer.MAX_VALUE;
        while (r < sLen) {
            ++r;
            if (r < sLen && osiMap.containsKey(s.charAt(r))) {
                cntMap.put(s.charAt(r), cntMap.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                // 判断当前开头字符是否是t中所含字符
                if (osiMap.containsKey(s.charAt(l))) {  // 开始滑动窗口
                    cntMap.put(s.charAt(l), cntMap.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check() {
        for (Map.Entry<Character, Integer> entry : osiMap.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if (cntMap.getOrDefault(key, 0) < value) return false;
        }
        return true;
    }

}

[AtaraxyAdong]

class Solution {
    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check() {
        Iterator iter = ori.entrySet().iterator(); 
        while (iter.hasNext()) { 
            Map.Entry entry = (Map.Entry) iter.next(); 
            Character key = (Character) entry.getKey(); 
            Integer val = (Integer) entry.getValue(); 
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        } 
        return true;
    }
}

[Jetery]

代码 (cpp)

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> cnt(128, 0);
        for (char c : t) cnt[c]++;

        int need = t.size();
        int size = s.size() + 1;
        int start = 0;
        int l = 0;
        for (int r = 0; r < s.size(); r++) {
            char c = s[r];
            if (cnt[c] > 0) need--;

            cnt[c]--;

            if (need != 0) continue;

            while (l < r && cnt[s[l]] < 0) {
                cnt[s[l]]++; 
                l++;
            }

            if (r - l + 1 < size) {
                size = r - l + 1;
                start = l;
            }

            cnt[s[l]]++;
            l++;
            need++;
        }

        return size != s.size() + 1 ? s.substr(start, start + size) : "";
    }
};

[zywang0]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l, counter, N, ct = 0, Counter(), len(s), Counter(t)
        k = 0
        ret, ans = inf, ""
        for r in range(N):
            counter[s[r]] += 1
            if s[r] in t and counter[s[r]] == ct[s[r]]:
                k += 1
            while k == len(ct):
                if r - l + 1 < ret:
                    ans = s[l:r+1]
                ret = min(r - l + 1, ret)
                counter[s[l]] -= 1
                if s[l] in t and counter[s[l]] == ct[s[l]]-1:
                    k -= 1
                l += 1
        return ans

[whoam-challenge]

class Solution: def minWindow(self, s: 'str', t: 'str') -> 'str': from collections import defaultdict lookup = defaultdict(int) for c in t: lookup[c] += 1 start = 0 end = 0 min_len = float("inf") counter = len(t) res = "" while end < len(s): if lookup[s[end]] > 0: counter -= 1 lookup[s[end]] -= 1 end += 1 while counter == 0: if min_len > end - start: min_len = end - start res = s[start:end] if lookup[s[start]] == 0: counter += 1 lookup[s[start]] += 1 start += 1 return res

[zrtch]

var minWindow = function(s, t) {
  const need = new Map(), window = new Map()
  for (const char of t) {
    if (!need.has(char)) {
      need.set(char,0)
      window.set(char,0)
    }
    need.set(char,need.get(char) + 1)
  }
  let left = 0, right = 0, rl = 0, rr = s.length, valid = 0, notChanged = true
  while (right < s.length) {
    const ins = s[right++]
    if (window.has(ins)) {
      window.set(ins, window.get(ins) + 1)
      if (window.get(ins) === need.get(ins)) valid++
    }
    while (valid === need.size) {
      if (right - left <= rr - rl) {
        rl = left
        rr = right
        notChanged = false
      }
      const del = s[left++]
      if (need.has(del)) {
        if (window.get(del) === need.get(del)) valid--
        window.set(del, window.get(del) - 1)
      }
    }
  }
  return notChanged ? '' : s.slice(rl,rr)
};