【Day 46 】2023-03-31 - 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 中存在这样的子串，我们保证它是唯一的答案。

[LIMBO42]

class Solution {
public:
    bool judge(unordered_map<char, int> &a, unordered_map<char, int> &target) {
        for(auto &it : target) {
            // cout<<it.first<<" ";
            // if(a.count(it.first) < target.count(it.first)) {
            //     return false;
            // }
            if(a.count(it.first) == 0 || a[it.first] < target[it.first]) {
                return false;
            }
        }
        // print(a);
        return true;
    }
    void print(unordered_map<char, int> &a) {
        for(auto &it : a) {
            cout<<it.first<<":"<<it.second<<" ";
        }
        cout<<endl;
    }
    string minWindow(string s, string t) {
        int l, r = 0;
        unordered_map<char, int> map;
        for(auto &ch : t) {
            map[ch]++;
        }
        for(; l < s.length(); ++l) {
            if(map.count(s[l])) {
                break;
            }
        }
        r = l;
        // cout<<"1";
        unordered_map<char, int> cur;
        string res = "";
        while(l < s.length() && r <= s.length()) {
            bool flag = judge(cur, map);
            if(flag == false) {
                cur[s[r]]++;
                r++;
                // if(r >= s.length()) break;
            }else {
                // r--;
                string tmp = s.substr(l, r-l);
                // cout<<tmp<<" ";
                if(res == "" || tmp.length() < res.length()) {
                    res = tmp;
                }
                // print(cur);
                cur[s[l]]--;
                l++;
                for(; l < s.length(); ++l) {
                    cur[s[l]]--;
                    if(map.count(s[l])) {
                        cur[s[l]]++;
                        break;
                    }
                }
                // print(cur);
                // cout<<l<<" ";
                // print(cur);
            }
        }
        // if(judge(cur, map)) {
        //     string tmp = s.substr(l, r-l);
        //     // cout<<tmp<<" ";
        //     if(res == "" || tmp.length() < res.length()) {
        //         res = tmp;
        //     }
        // }
        return res;
    }
};

[kofzhang]

思路

滑动窗口，和昨天的题差不多 用diff记录是否符合结果 右指针右移，期间计算左指针可不可以右移，每次计算长度是否比预设长度小，如果小，更新最小长度，并记录结果

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        left = 0
        right = 0
        curmax = float(inf)
        c = Counter(t)
        diff = sum(c.values())
        resleft = 0
        resright = 0
        while right<len(s):
            if s[right] in c:
                if c[s[right]]>0:
                    diff -= 1
                c[s[right]]-=1
            else:
                right +=1
                continue
            while (left<len(s)) and ((s[left] not in c) or (c[s[left]]<0)):
                if s[left] in c and c[s[left]]<0:
                    c[s[left]]+=1
                left += 1
            if diff == 0 and right-left+1<curmax:
                curmax = right-left+1
                resleft = left
                resright = right
            right += 1
        return s[resleft:resright+1] if curmax<=len(s) else ""

[wangzh0114]

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;
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = INT_MAX;
        while (right < s.size()) {
            // c 是将移入窗口的字符
            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;
                }
                // d 是将移出窗口的字符
                char d = s[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.count(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
                }                    
            }
        }
        // 返回最小覆盖子串
        return len == INT_MAX ?
            "" : s.substr(start, len);
    }
};

• TC:O(N)
• SC:O(N)

[JiangyanLiNEU]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        d = Counter(t)
        c = len(d)
        i = start = 0
        n = len(s)
        ans = n+1
        for j in range(n):
            if s[j] in d:
                d[s[j]]-=1
                if d[s[j]]==0:
                    c-=1            
            while c==0:
                if ans>j-i+1:
                    ans=j-i+1
                    start=i
                if s[i] in d:
                    d[s[i]]+=1
                    if d[s[i]]>0:
                        c+=1
                i+=1
        if ans>n:
            return ""
        return s[start:start+ans]

[bookyue]

TC: O(n)
SC: O(1)

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

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

        int right = 0;
        int left = 0;
        int start = 0;
        int len = s.length() + 1;
        while (right < s.length()) {
            if (cnt[s.charAt(right)]-- == 1) diff--;
            right++;

            while (diff == 0) {
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }

                if (cnt[s.charAt(left)]++ == 0) diff++;
                left++;
            }
        }

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

[SoSo1105]

class Solution: def minWindow(self, s: str, t: str) -> str: d = Counter(t) c = len(d) i = start = 0 n = len(s) ans = n+1 for j in range(n): if s[j] in d: d[s[j]]-=1 if d[s[j]]==0: c-=1
while c==0: if ans>j-i+1: ans=j-i+1 start=i if s[i] in d: d[s[i]]+=1 if d[s[i]]>0: c+=1 i+=1 if ans>n: return "" return s[start:start+ans]

[linlizzz]

思路

滑动窗口 + 哈希表记录字符个数，并确定左边界的滑动条件

代码

（看了官方题解）

from collections import Counter
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 = r - l + 1
                counter[s[l]] -= 1
                if s[l] in t and counter[s[l]] == ct[s[l]]-1:
                    k -= 1
                l += 1
        return ans

复杂度分析

T(n) = O(len(s)+len(t))

S(n) = O(n)，n为t中不重复字符数

[wangqianqian202301]

思路

代码

from collections import Counter
from collections import deque

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_counts = Counter(t)
        w = Counter()
        r = ''
        window = deque()
        for ch in s:
            window.append(ch)
            w[ch] += 1
            if all(w[c] >= t_counts[c] for c in t_counts.keys()):
                while window and w[window[0]] > t_counts[window[0]]:
                    w[window.popleft()] -= 1
                if r == '' or len(window) < len(r):
                    r = ''.join(window)
                if window:
                    w[window.popleft()] -= 1
        return r

s = Solution()
print(s.minWindow("abcdefg", "ac"))

复杂度

[Meisgithub]

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> tMap;
        for (const auto &c : t)
        {
            tMap[c]++;
        }
        unordered_map<char, int> sMap;
        int n = s.size();
        int left = 0, right = 0;
        int minLen = INT_MAX, start = 0;
        while (right < n)
        {
            sMap[s[right]]++;
            right++;
            while (check(sMap, tMap) && left < right)
            {
                if (right - left < minLen)
                {
                    minLen = right - left;
                    start = left;
                }
                sMap[s[left]]--;
                left++;
            }
        }
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }

    bool check(unordered_map<char, int> &sMap, unordered_map<char, int> &tMap)
    {
        for (const auto &[key, value] : tMap)
        {
            if (sMap[key] < value)
            {
                return false;
            }
        }
        return true;
    }
};

[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

[FireHaoSky]

思路：滑动窗口，哈希表

代码：python

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        needs = defaultdict(int)
        for i in t:
            needs[i] += 1
        nCount = len(t)
        l = 0
        res = (0, float('inf'))

        for r, v in enumerate(s):
            if needs[v] > 0:
                nCount -= 1
            needs[v] -= 1

            if nCount == 0:
                while True:
                    v  = s[l]
                    if needs[v] == 0:
                        break
                    needs[v] += 1
                    l += 1

                if r - l < res[1] - res[0]:
                    res = (l, r)
                needs[s[l]] += 1
                nCount += 1
                l += 1
        return '' if res[1] > len(s) else s[res[0]:res[1]+1]

复杂度分析：

"""
时间复杂度：O(n)
空间复杂度：O(s+t)
"""

[JadeLiu13]

采用类似滑动窗口的思路，即用两个指针表示窗口左端left和右端right。 向右移动right，保证left与right之间的字符串足够包含需要包含的所有字符， 而在保证字符串能够包含所有需要的字符条件下，向右移动left，保证left的位置对应为需要的字符，这样的 窗口才有可能最短，此时只需要判断当期窗口的长度是不是目前来说最短的，决定要不要更新minL和minR

移动right的时候，碰到t中的一个字符，对应字典的计数就减一，那么当字典这些元素的值都不大于0的时候，窗口里面就包含了所有需要的字符

移动left，直到找到目标字符串中的字符，同时又希望窗口尽可能短，因此希望找到的left使得窗口的开头就是要求的字符串中的字符，同时整个窗口含有所有需要的字符数量

from collections import defaultdict
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        #s的长度必须不小于t
        if len(s) < len(t): return ''
        #初始化
        rec = defaultdict(int)
        len_t = len(t)
        minLeft, minRight = 0, len(s)

        #记录t中各个字母的出现频次
        for i in t:
            rec[i] += 1

        #开始寻找子串
        left = 0
        for right, str in enumerate(s):
            if rec[str] > 0:  #找到t中的字母,对于不存在的valu而等于0（这就是defaultdic的方便之处）
                len_t -= 1
            rec[str] -= 1 #值为负的要么是多余的在t中的字符，要么是不在t中的字母，便于后面left移动

            if  len_t == 0:
                while rec[s[left]] < 0: #值为负的要么是多余的在t中的字符，要么是不在t中的字母，left向右移动
                    rec[s[left]] += 1
                    left += 1

                if right - left < (minRight - minLeft):  #上一步left到位，现在更新最小区间
                    minLeft, minRight = left, right

                rec[s[left]] += 1 # 开始找下一个窗口
                left += 1
                len_t += 1

        return '' if minRight == len(s) else s[minLeft:minRight+1]

[Bochengwan]

class Solution { public int maxVowels(String s, int k) { int n = s.length(); int vowel_count = 0; for (int i = 0; i < k; ++i) { vowel_count += isVowel(s.charAt(i)); } int ans = vowel_count; for (int i = k; i < n; ++i) { vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k)); ans = Math.max(ans, vowel_count); } return ans; }

public int isVowel(char ch) {
    return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
}

}

[duke-github]

思路

滑动窗口

复杂度

时间复杂度 O(C*|s|+|t|) 空间复杂度O(C)

代码

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

[bingzxy]

思路

滑动窗口

代码

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        boolean[] exists = new boolean[128];
        int[] arr = new int[128];
        for (char c : t.toCharArray()) {
            exists[c] = true;
            arr[c]++;
        }

        int cnt = 0, left = 0, right = 0, minLen = s.length() + 1, minIndex = 0;
        for (; right < s.length(); right++) {
            if (exists[s.charAt(right)]) {
                arr[s.charAt(right)]--;
                if (arr[s.charAt(right)] >= 0) {
                    cnt++;
                }

                while (cnt == t.length()) {
                    if (minLen > right - left + 1) {
                        minLen = right - left + 1;
                        minIndex = left;
                    }
                    if (exists[s.charAt(left)]) {
                        arr[s.charAt(left)]++;
                        if (arr[s.charAt(left)] > 0) {
                            cnt--;
                        }
                    }
                    left++;
                }
            }
        }
        return minLen > s.length() ? "" : s.substring(minIndex, minIndex + minLen);
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(C)，C 为字符集大小

[xb798298436]

public String minWindow(String s, String t) {

Map<Character, Integer> map = new HashMap<>();

int num = t.length();

for (int i = 0; i < num; i++)
    map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) - 1);

int len = Integer.MAX_VALUE, match = 0, resLeft = 0, resRight = 0;

int left = 0, right = 0;

while (right < s.length()) {

    char ch = s.charAt(right);

    if (map.containsKey(ch)) {

        int val = map.get(ch) + 1;
        if (val <= 0)
            match++;
        map.put(ch, val);
    }

    while (match == num) {

        if (right - left + 1 < len) {

            len = right - left + 1;
            resLeft = left;
            resRight = right;
        }

        char c = s.charAt(left);
        if (map.containsKey(c)) {

            int val = map.get(c) - 1;
            if (val < 0)
                match--;
            map.put(c, val);
        }

        left++;
    }

    right++;
}

return len == Integer.MAX_VALUE ? "" : s.substring(resLeft, resRight + 1);

}

[aoxiangw]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""
        countT, window = {}, {}
        for c in t:
            countT[c] = 1 + countT.get(c, 0)

        l = 0
        res, resLen = [-1,-1], float("inf")
        have, need = 0, len(countT)

        for r in range(len(s)):
            c = s[r]
            window[c] = 1 + window.get(c, 0)

            if c in countT and window[c] == countT[c]:
                have += 1

            while have == need:
                if (r - l + 1) < resLen:
                    res = [l, r]
                    resLen = r - l + 1
                window[s[l]] -= 1
                if s[l] in countT and window[s[l]] < countT[s[l]]:
                    have -= 1
                l += 1

        l, r = res
        return s[l:r+1] if resLen != float("inf") else ""

O(s+t), O(t)

[Hughlin07]

class Solution {

public String minWindow(String s, String t) {

    if (s.length() == 0 || t.length() == 0) {
        return "";
    }

    Map<Character, Integer> dictT = new HashMap<Character, Integer>();

    for (int i = 0; i < t.length(); i++) {
        int count = dictT.getOrDefault(t.charAt(i), 0);
        dictT.put(t.charAt(i), count + 1);
    }

    int required = dictT.size();

    List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (dictT.containsKey(c)) {
            filteredS.add(new Pair<Integer, Character>(i, c));
        }
    }

    int l = 0, r = 0, formed = 0;
    Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
    int[] ans = { -1, 0, 0 };

    while (r < filteredS.size()) {
        char c = filteredS.get(r).getValue();
        int count = windowCounts.getOrDefault(c, 0);
        windowCounts.put(c, count + 1);

        if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
            formed++;
        }

        while (l <= r && formed == required) {
            c = filteredS.get(l).getValue();

            int end = filteredS.get(r).getKey();
            int start = filteredS.get(l).getKey();
            if (ans[0] == -1 || end - start + 1 < ans[0]) {
                ans[0] = end - start + 1;
                ans[1] = start;
                ans[2] = end;
            }

            windowCounts.put(c, windowCounts.get(c) - 1);
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                formed--;
            }
            l++;
        }
        r++;
    }
    return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}

}

[JasonQiu]

• Sliding window

  class Solution:
  def minWindow(self, s: str, t: str) -> str:
      freq = defaultdict(int)
      result = [-1, 100001] # [left, length]
      n_diff_chars = 0
      for c in t:
          freq[c] += 1
          if freq[c] == 1:
              n_diff_chars += 1
      left = 0
      for right in range(len(s)):
          freq[s[right]] -= 1
          if freq[s[right]] == 0:
              n_diff_chars -= 1
          if n_diff_chars == 0:
              while freq[s[left]] < 0:
                  freq[s[left]] += 1
                  left += 1
              if result[0] == -1 or right - left < result[1]:
                  result = [left, right - left]
      return s[result[0]:(result[0] + result[1] + 1)] if result[0] >= 0 else ""

  Time: O(m + n) Space: O(1)

[lp1506947671]

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

复杂度分析

• 时间复杂度：O(N + K)，N 为 S 串长度，K 为 T 串长度
• 空间复杂度：O(S)，其中 S 为 T 字符集元素个数

[harperz24]

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

[chanceyliu]

代码

function minWindow(s: string, t: string): string {
  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;
}

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[jiujingxukong]

思路

我本来没看出跟昨天的滑动窗口的题目有什么不同，为什么是hard题。
直接复制讲义：读完该题，是否发现和前一天的题目有些类似呢，前一天的那个说法叫异位词，今天这个直接说包含 T 的所有字符，意思其实是一样的，那不一样的在哪呢？

• 这次的窗口长度并不固定为 T 的长度，实际窗口大小是 ≥T.length 的
• 这次输出的是最小子串，也就是长度最小的子串，因此我们要维护一个 min，代表当前符合要求的子串长度，遇到更短的，则进行更新。

要注意字符串实例substr的用法。

js代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  const hashTable = new Map();
  const window = new Map();
  for (let i of t) {
    hashTable.set(i, (hashTable.get(i) || 0) + 1);
  }
  let left = 0;
  let right = 0;
  let valid = 0;
  let start = 0;
  let len = Infinity;
  while (right < s.length) {
    let c = s[right];
    right++;
    if (hashTable.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === hashTable.get(c)) {
        valid++;
      }
    }

    while (valid === hashTable.size) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      let d = s[left];
      left++;
      if (hashTable.has(d)) {
        if (window.get(d) === hashTable.get(d)) {
          valid--;
        }
        window.set(d, window.get(d) - 1);
      }
    }
  }
  return len === Infinity ? "" : s.substr(start, len);
};

复杂度分析

m是s长度，n是t长度。

1. TC：O（m+n）
2. SC：O（n）

[NorthSeacoder]

var minWindow = function(s, t) {
    const map = {};
    let count = t.length;
    // 统计字符串 t 中每个字符的出现次数
    for (const c of t) {
        map[c] = (map[c] || 0) + 1;
    }
    let left = 0,
        start = -1,
        len = Infinity;
    // 用右指针扫描字符串 s
    for (let right = 0; right < s.length; right++) {
        const cur = s[right];
        // 若 map 中存在该字符，则将该字符出现次数减1
        if (map[cur] !== undefined) {
            count -= map[cur] > 0 ? 1 : 0;
            map[cur]--;
        }
        // 当所有字符都被包含时，将左指针向右移动
        while (count === 0) {
            // 若当前子串长度更小，则更新子串的起始位置和长度
            if (right - left + 1 < len) {
                start = left;
                len = right - left + 1;
            }
            // 若 map 中存在该字符，则将该字符出现次数加1
            const char = s[left];
            if (map[char] !== undefined) {
                count += map[char] === 0 ? 1 : 0;
                map[char]++;
            }
            // 将左指针向右移动
            left++;
        }
    }
    return start === -1 ? '' : s.substring(start, start + len);
};

• TC: O(n)
• SC:O(1)

[RestlessBreeze]

code

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

[kangliqi1]

class Solution { public String minWindow(String s, String t) { if (s.length() < t.length()) { return ""; } boolean[] exists = new boolean[128]; int[] arr = new int[128]; for (char c : t.toCharArray()) { exists[c] = true; arr[c]++; }

    int cnt = 0, left = 0, right = 0, minLen = s.length() + 1, minIndex = 0;
    for (; right < s.length(); right++) {
        if (exists[s.charAt(right)]) {
            arr[s.charAt(right)]--;
            if (arr[s.charAt(right)] >= 0) {
                cnt++;
            }

            while (cnt == t.length()) {
                if (minLen > right - left + 1) {
                    minLen = right - left + 1;
                    minIndex = left;
                }
                if (exists[s.charAt(left)]) {
                    arr[s.charAt(left)]++;
                    if (arr[s.charAt(left)] > 0) {
                        cnt--;
                    }
                }
                left++;
            }
        }
    }
    return minLen > s.length() ? "" : s.substring(minIndex, minIndex + minLen);
}

}

[DragonFCL]

var minWindow = function(s, t) {
    const needs = {},
    window = {};
  for (const c of t) {
    if (needs[c] === undefined) {
      needs[c] = 0;
    }
    needs[c]++;
    window[c] = 0;
  }
  const needsSize = Object.keys(needs).length;

  let left = 0,
    right = 0;
  let valid = 0;
  let start = 0,
    len = Infinity;
  while (right < s.length) {
    const c = s[right];
    right++;
    if (needs[c] !== undefined) {
      window[c]++;
      if (window[c] === needs[c]) {
        valid++;
      }
    }
    while (valid === needsSize) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      const d = s[left];
      left++;
      if (needs[d] !== undefined) {
        if (window[d] === needs[d]) valid--;
        window[d]--;
      }
    }
  }
  return len === Infinity ? "" : s.substr(start, len);
};

[tzuikuo]

思路

滑动窗口

代码

class Solution {
public:
    string minWindow(string s, string t) {
        int n=s.size(),nt,i=0,mini=n+1,ii,jj;
        map<char,int> mt;
        string result;

        for(auto it:t) mt[it]++;
        nt=mt.size();
        for(int j=0;j<n;j++){
            mt[s[j]]--;
            if(mt[s[j]]==0) nt--;
            //cout<<"j="<<j<<" ";
            while(nt==0){
                mt[s[i]]++;
                if(mt[s[i]]>0) nt++;            
                if(j-i+1<mini){
                    mini=j-i+1;
                    ii=i;
                    jj=j;
                }
                i++;
            }
        }
        for(int k=ii;k<=jj;k++){
            result.push_back(s[k]);
        }
        return result;
    }
};

复杂度分析 待定

[Fuku-L]

代码

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || s == "" || t == null || t == "" || s.length() < t.length()){
            return "";
        }
        int[] tCnt = new int[128];
        int[] sCnt = new int[128];
        // 统计目标字符串中的字符数量
        int tLen = t.length();
        int sLen = s.length();
        for(int i = 0; i< tLen; i++){
            tCnt[t.charAt(i)]++;
        }
        int left = 0, right = 0, min = sLen + 1;
        int count = 0, start = 0;
        while(right < sLen){
            char ch = s.charAt(right);
            if(tCnt[ch] == 0){
                right++;
                continue;
            }
            if(sCnt[ch] < tCnt[ch]){
                count++;
            }
            sCnt[ch]++;
            right++;
            while(count == tLen){
                if(right - left < min){
                    min = right - left;
                    start = left;
                }
                char l = s.charAt(left);
                if(tCnt[l] == 0){
                    left++;
                    continue;
                }
                if(sCnt[l] == tCnt[l]){
                    count--;
                }
                sCnt[l]--;
                left++;
            }
        }
        if(min == sLen + 1){
            return "";
        }
        return s.substring(start, start+min);
    }
}

[Lydia61]

76. 最小覆盖字串

思路

参考官方滑动窗口法

代码

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

复杂度分析

• 时间复杂度：O(C⋅∣s∣+∣t∣)
• 空间复杂度：O(C)

[X1AOX1A]

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

[Jetery]

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> ms, mt;
        for (char x : t) {
            mt[x]++;
        }
        string ans;
        for (int i = 0, j = 0, c = 0; i < s.size(); i++) {
            ms[s[i]]++;
            if (ms[s[i]] <= mt[s[i]]) c++;
            while (j < i && ms[s[j]] > mt[s[j]]) ms[s[j++]]--;
            if (c == t.size() && (ans.empty() || i - j + 1 < ans.size())) {
                ans = s.substr(j, i - j + 1);
            }
        }
        return ans;
    }
};

[AstrKing]

代码

class Solution {
    public String minWindow(String s, String t) {
        String res = "";
        if (t.length() > s.length()) {
            return res;
        }
        // need 是需要凑齐的字符
        HashMap<Character, Integer> need = new HashMap<>();
        // window 当前是当前窗口有几个字符
        HashMap<Character, Integer> window = new HashMap<>();
        // 遍历我们的需要覆盖的字符串，将结果加入至need 哈希表中
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        }
        // left 起点
        int l = 0;
        // right 终点
        int r = 0;
        // 已经满足的字符个数，那么当valid的值 == t.size()时，那么就说明已经满足该窗口了
        int valid = 0;
        // 最大值
        int len = Integer.MAX_VALUE;
        // 其实位置，我们从0开始
        int start = 0;
        // 只要right没有超过s的边界，就无脑遍历
        while (r < s.length()) {
            // 这个是加进来的字符值
            char ch = s.charAt(r);
            // 加进来一个字符，那么right往右边移动一个位置
            r++;
            // 只有当该值在need里面时，我们才往里面加东西
            if (need.containsKey(ch)) {
                // 那么窗口里面先累加，这个时候只考虑我们需要的值，其它值不用考虑，反正有start起始位置，最后直接字符串截取即可
                window.put(ch, window.getOrDefault(ch, 0) + 1);
                // 如果窗口里面某个值的个数 == 需要的值的个数，那么说明我们其中一个满足了
                if (window.get(ch).equals(need.get(ch))) {
                    // valid就++
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            // 当valid的值 == need的size，size就是key，就是distint字符的种类，都满足了，那说明就是有效了，该窗口肯定就符合了
            // 那么我们开始收缩左窗口
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                // 趁着满足条件了，我们先更新再说，更新就更新一下其实位置和长度即可
                if (r - l < len) {
                    start = l;
                    len = r - l;
                }
                // d 是将移出窗口的字符
                // 取来，下面是要用的
                char d = s.charAt(l);
                // 左移窗口，无脑左移，我管你成功不成功，那不是我操心的事儿，你后面自己判断去吧
                l++;
                // 进行窗口内数据的一系列更新
                // 判断在不在里面，不在，皆大欢喜，我继续左移，在的话就进去判断
                // 进去了，不一定出来，可能中间加了多个，减去一个也没事儿
                if (need.containsKey(d)) {
                    // 我们进行判断，如果说，== 了，那么就说明再移除这个值就打破平衡了，那么我们就跳出来
                    if (window.get(d).equals(need.get(d))) {
                        // valid -- ,直接跳出来，反正上面的while 是valid == need.size()
                        valid--;
                    }
                    // 这个是不管你是否对valid进行操作，我就把窗口里面的这个值的个数减一，我个人感觉这个
                    // 放在判断valid是否--上面比较好，先搞那些无脑的操作，再进行比对，多顺畅
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        //  最后就是跳出来了，我们看下lec的长度是否还是我们的初始最大值，如果是，那么就说明一次都没进去过
        //  如果不是，那么就截取我们定的最小长度的start和长度，进行相关的截取操作即可
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

[snmyj]

class 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

[yingchehu]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        def fullfill(seen, target):
            if len(seen) != len(target):
                return False
            for k in target:
                if seen[k] < target[k]:
                    return False
            return True

        l = 0
        ans = ""
        seen = collections.defaultdict(int)
        target = collections.Counter(t)

        for r in range(len(s)):
            if s[r] in target:
                seen[s[r]] += 1

            while l <= r and fullfill(seen, target):
                candidate = s[l:r+1]
                if len(candidate) < len(ans) or len(ans) == 0:
                    ans = candidate                
                if s[l] in seen:
                    seen[s[l]] -= 1
                    if seen[s[l]] == 0:
                        del seen[s[l]]
                l += 1

        return ans

[chocolate-emperor]

class Solution {
public:
    string minWindow(string s, string t) {
        int len_s = s.length(), len_t = t.length();
        int letter_s[128]={0},letter_t[128] = {0};
        for(auto i:t){
            letter_t[i] +=1;
        }
        if(len_t>len_s) return "";

        int l = 0;
        string res = "";

        for(int r = 0; r < len_s; r++){
            //扩展窗口，记录字母数
            letter_s[s[r]] +=1;

            //满足条件的情况下，收缩窗口大小
            while(r - l + 1 > len_t && letter_s[s[l]] > letter_t[s[l]]) {
                letter_s[s[l]] -= 1;
                l+=1;
            }

            //结算是否是substring
            bool flag = true;
            for(int i = 0;i<128;i++){
                if(letter_s[i]<letter_t[i])    flag =false;
            }

            //注意最初res为""
            if(flag && res.length()==0)  res = s.substr(l,r-l+1);
            else if(flag && r-l+1<res.length()) res = s.substr(l,r-l+1);
            //printf("%%d %d\n",l,r);
        }
        return res;
    }
};