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

[yan0327]

思路： 滑动窗口，由于是覆盖字串。首先右移窗口找符合条件的值，满足条件后则左移窗口。 PS：判定标准是哈希表记录的值和 出现的次数

func minWindow(s string, t string) string {
    if len(s) < len(t){
        return ""
    }
    out := ""
    var have [58]int
    var find [58]int
    valid := 0
    cur := 0
    for i:=0;i<len(t);i++{
        if have[t[i]-'A'] == 0{
            valid++
        }
        have[t[i]-'A']++
    }
    l,r := 0,-1
    for l < len(s){
        if (r+1)<len(s)&&valid != cur{
            r++
            find[s[r]-'A']++
            if find[s[r]-'A'] == have[s[r]-'A']{
                cur++
            }
        }else{
            find[s[l]-'A']--
            if find[s[l]-'A'] == have[s[l]-'A']-1{
                cur--
            }
            l++
        }
        if cur == valid{
            if out == ""|| len(out) > r-l+1{
                out = s[l:r+1]
            }
        }
    }
    return out
}

时间复杂度：O（N） 空间复杂度：O（C）

[zwx0641]

class Solution { public String minWindow(String s, String t) { int[] chars = new int[128]; boolean[] check = new boolean[128]; for (char c : t.toCharArray()) { chars[c]++; check[c] = true; } int l = 0, r = 0, size = s.length() + 1, min_l = 0; int window = 0; while (r < s.length()) { if (check[s.charAt(r)]) { if (--chars[s.charAt(r)] >= 0) { window++; } } r++;

        while (window == t.length()) {
            if (r - l < size) {
                size = r - l;
                min_l = l;
            }
            if (check[s.charAt(l)] && ++chars[s.charAt(l)] > 0) {
                window--;
            }
            l++;
        }
    }
    return size == s.length() + 1 ? "" : s.substring(min_l, min_l + size);
}

}

[laofuWF]

# sliding window
# move left pointer when left letter exceed count required for t, 
# meaning we do not need that letter in the window
# check count (valid number of letters in the current window) to find candidate substring

# time: O(N), len(s)
# space: O(M), number of unique letters in t

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        letters = defaultdict(int)
        for letter in t:
            letters[letter] += 1
        if len(s) < len(t):
            return ""

        res = ""
        left = 0
        right = 0
        while left < len(s) and not s[left] in t:
            left += 1
            right += 1

        # valid letters in curr substring
        count = 0

        while right < len(s):
            if s[right] in letters:
                letters[s[right]] -= 1
                if letters[s[right]] >= 0:
                    count += 1

                # move left when letter at left index is exceed max count of that letter
                while (s[left] in letters and letters[s[left]] < 0) or not s[left] in letters:
                    if s[left] in letters:
                        letters[s[left]] += 1
                        if letters[s[left]] > 0:
                            count -= 1
                    left += 1

                # check count for candidate
                if count == len(t) and (res == "" or (right - left + 1) < len(res)):
                    res = s[left:right + 1]

            right += 1

        return res

[Bochengwan]

思路

通过sliding window，比较目标字符串的dict和当前window内字符串window的dict.

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s or len(t)>len(s):
            return ''
        my_map = dict(collections.Counter(t))
        ans = ''
        ans_length = float('inf')
        correct_number = len(my_map)
        l,r = 0, len(t)
        curr = collections.defaultdict(int)
        for e in s[l:r]:
            if e in my_map:
                curr[e]+=1
        if curr == my_map:
            return s[l:r]
        for k,v in my_map.items():
            if curr[k]>=v:
                correct_number -=1
        while r<len(s):
            if s[r] in my_map:
                curr[s[r]]+=1
                if curr[s[r]] == my_map[s[r]]:
                    correct_number-=1
            while correct_number == 0 and l<=r:
                if s[l] in my_map:
                    if ans_length>(r-l+1):
                        ans_length = r-l+1
                        ans = s[l:r+1]

                    curr[s[l]]-=1
                    if curr[s[l]]<my_map[s[l]]:
                        correct_number+=1
                l+=1
            r+=1
        return ans

复杂度分析

• 时间复杂度：O(len(s)+len(t))，其中 N 为数组长度。
• 空间复杂度：O(len(s)+len(t))

[yetfan]

思路 字典计数来判断是否为子串 滑动窗口双指针 l = 0，r = len(t), 如果不满足条件就向右移动r，扩充窗口大小。 如果满足条件就向右移动l，尝试寻找更小解。

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l = 0
        r = len(t) - 1
        min_len = inf
        res = (0,0)
        if len(s) < len(t):
            return ""

        s_ele = collections.defaultdict(int)
        t_ele = collections.defaultdict(int)

        def check(sdict, tdict):
            for i in tdict:
                if sdict[i] < tdict[i]:
                    return False
            return True

        for i in range(len(t)):
            s_ele[ord(s[i]) - ord('a')] += 1
            t_ele[ord(t[i]) - ord('a')] += 1

        if check(s_ele, t_ele):
            return s[:r+1]

        while r < len(s):
            if check(s_ele, t_ele):
                if r - l + 1 < min_len:
                    min_len = r - l + 1
                    res = (l,r)
                s_ele[ord(s[l]) - ord('a')] -= 1
                l += 1              
            else:
                r += 1
                if r == len(s):
                    break
                s_ele[ord(s[r]) - ord('a')] += 1

        if res[1] == 0:
            return ""
        else:
            return s[res[0]:res[1]+1]

复杂度 时间 O(lens+lent) 空间 O(c)

[charlestang]

思路

滑动窗口

我们可以用一个哈希来存储 T 中所有字母出现的频次。

然后，我们使用一个滑动窗口来遍历 S。left 指针和 right 指针从 0 出发。

每次循环，我们把 right 指针指向的字母加入 window，如果能覆盖 T，那么就把 left 指针前移，直到不能覆盖，记录当前最小长度和起止位置。

重复这个过程，直到遍历完 S。

时间复杂度 $O(n)$ 因为左右指针都各扫描 S 一遍。因为字母表是常数数量，所以确认 window 能否覆盖 T，需要常数时间。

空间复杂度 $O(n)$，最坏情况下，全部的 S 都无法覆盖 T，则 S 所有的字符都会加入到 window 中。

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        tset = [0] * 58
        for c in t:
            k = ord(c) - ord('A')
            tset[k] += 1

        wset = [0] * 58

        def check():
            for k,v in enumerate(tset):
                if v > 0:
                    if wset[k] < v:
                        return False
            else:
                return True
        st = en = 0
        ans = len(s) + 1
        minst = minen = 0
        while st < len(s):
            k = ord(s[st]) - ord('A')
            if tset[k] == 0:
                st += 1
                continue
            wset[k] += 1
            while en <= st and check():
                if st - en + 1 < ans:
                    ans = st - en + 1
                    minst = st
                    minen = en
                k = ord(s[en]) - ord('A')
                if wset[k] > 0:
                    wset[k] -= 1
                en += 1
            st += 1
        return s[minen: minst + 1] if ans <= len(s) else ""

[ZacheryCao]

Idea

Sliding Window

Code

#include <iostream>
#include <map>
using namespace std;
class Solution {
public:
    string minWindow(string s, string t) {
        int s_len = s.size(), t_len = t.size();
        if(t_len > s_len) return "";
        vector<int> s_count(128, 0);
        vector<int> t_count(128, 0);
        for(auto i:t) t_count[i]++; 
        int si = -1, start = 0, mx = INT_MAX, c = 0;
        for(int i = 0; i<s_len; i++){
            s_count[s[i]]++;
            if(t_count[s[i]]!=0 && s_count[s[i]]<=t_count[s[i]]) c++;
            if(c==t_len)
            {
                while(t_count[s[start]] == 0 || t_count[s[start]]<s_count[s[start]])
                {
                    s_count[s[start]]--;
                    start++;
                }
                if(i-start+1<mx)
                {
                    mx = i-start+1;
                    si = start;
                }
            }

        }
        return si==-1?"":s.substr(start,mx);
    }
};

Complexity:

Time: O(S+P) Space: O(S+P)

[chakochako]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        needs = {}
        window = {}
        left = right = 0
        start = 0
        length = len(s) + 1
        valid = 0

        for i in t:
            needs[i] = needs.get(i,0) + 1

        while right < len(s):
            cur = s[right]
            #print(valid)
            #print(left, right)
            if cur in needs:
                window[cur] = window.get(cur,0) + 1 #如果字母在needs中，计数，如果不在不用计数
                if window[cur] == needs[cur]: #如果特定字母的数量已经等于需要的数量，valid 增加1
                    valid = valid + 1

            while valid == len(needs): # 注意，len(needs) 计算unique的字母的数量
                #print(right - left)
                if (right - left) < length:
                    start = left
                    length = right - left

                if needs.get(s[left]):
                    window[s[left]] = window[s[left]] - 1
                    if window[s[left]] < needs[s[left]]:
                        valid = valid - 1            
                left = left + 1
            right = right + 1

        #print(start, length)
        return s[start:start + length + 1] if length != len(s) + 1 else ""

[xvectorizer]

滑动窗口，用l, r作为左右指针，维护窗口，向右移动 用backet记录当前窗口包含元素的个数，用target记录目标字符串包含元素的个数，用valid记录当前符合的元素个数，这样不用每次一一比较了 判断左指针还是右指针移动？如果当前窗口包含目标，左指针移动，争取缩小窗口。如果不包含，右指针移动才有可能能满足条件

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l = 0
        r = 0
        ans = None
        valid = 0
        backet = defaultdict(int)
        target = defaultdict(int)

        for i in t:
            target[i] += 1

        while r < len(s) or l < len(s):
            if r < len(s) and len(target) > valid:
                if s[r] in target:
                    backet[s[r]] += 1
                    if backet[s[r]] == target[s[r]]:
                        valid += 1
                r += 1

            else:
                if s[l] in backet:
                    backet[s[l]] -= 1
                    if backet[s[l]] + 1 == target[s[l]]:
                        valid -= 1
                l += 1

            if len(target) == valid:
                    if not ans or r - l < len(ans):
                        ans = s[l: r]

        return ans if ans else ''

[zwmanman]

class Solution(object): def minWindow(self, s, t): """ :type s: str :type t: str :rtype: str """ l = r = 0 start = end = 0 res_len = float('inf') need = collections.Counter(t) window = collections.defaultdict(int) valid = 0

    while r < len(s):
        c = s[r]
        r += 1

        if c in need:
            window[c] += 1

            if window[c] == need[c]:
                valid += 1

        while valid == len(need):
            if r - l < res_len:
                start = l
                end = r
                res_len = r - l

            d = s[l]
            l += 1

            if d in need:

                if window[d] == need[d]:
                    valid -= 1

                window[d] -= 1

    if res_len == float('inf'):
        return ""
    else:

        return s[start: end]

[MonkofEast]

76. Minimum Window Substring

Click Me

Algo

1. As in comments

Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l, n = 0, len(s)
        liveCnt, tCnt = Counter(), Counter(t)

        # indicate whether we have found all the char in t in curr window
        k = 0

        ret, res = float('inf'), ""
        for r in range(n):
            # 1. right: move 1 step
            liveCnt[s[r]] += 1
            # 2. if curr char is in t, and the cnt of this char is enough
            # we mark it as this char has been satisfied
            if s[r] in t and liveCnt[s[r]] == tCnt[s[r]]: k += 1
            # 3. if all char has been satisfied
            while k == len(tCnt):
                # a) if curr window is shorter than previous satisfed window
                if r - l + 1 < ret:
                    # we update res
                    res = s[l:r + 1]
                # and update min length
                ret = min(ret, r - l + 1)
                # b) try to shrink the left
                # update counting
                liveCnt[s[l]] -= 1
                # update all char satisfied indicator
                if s[l] in t and liveCnt[s[l]] == tCnt[s[l]] - 1: k -= 1
                # move left 1 step
                l += 1

        return res

Comp

T: O(len(s) + len(t))

S: O(len(set(t)))

[ZhangNN2018]

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        l, counter, N, ct = 0, Counter(), len(s), Counter(t)
        k = 0
        ret, ans = float('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

[feifan-bai]

思路

1. 滑动窗口 + Hashmap

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        lookup = defaultdict(int)
        for c in t:
            lookup[c] += 1
        start, end = 0, 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

复杂度分析

• 时间复杂度：O(n), n = s + t
• 空间复杂度：O(k), k = count(t)

[freesan44]

思路

滑动窗口

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        length = len(s)
        left,right,match = 0, 0,0
        resLeft,resRight,minResLen = 0, 0,length+1
        tDict = Counter(t)
        while right < length:
            #先右边扩张
            # print(left, right, resLeft, resRight)
            # print([s[left:right+1]])
            rS = s[right]
            # print(rS,tDict)
            if rS in tDict:
                tDict[rS] -= 1
                if tDict[rS] >= 0:
                    match += 1
            #收缩条件
            while match == len(t):
                #判断是否最短子串长度
                if (right - left) < minResLen:
                    # print([s[left:right + 1]],resRight,resLeft, minResLen)
                    minResLen = min(minResLen,right-left)
                    resLeft,resRight = left,right
                #左边在收缩，直到mtath<len(t)
                if left <= right:
                    lS = s[left]
                    if lS in tDict:
                        tDict[lS] += 1
                        if tDict[lS] > 0:
                            match -= 1
                        # print(lS, tDict)
                    left += 1
            right += 1
        # print(left, right, resLeft, resRight)
        return s[resLeft:resRight+1] if minResLen != length+1 else ""

if __name__ == '__main__':
    s = "ADOBECODEBANC"
    t = "ABC"
    s = "a"
    t = "a"
    result = Solution().minWindow(s,t)
    print(result)

复杂度分析

令 n 为数组长度。

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

[ginnydyy]

Problem

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

Notes

• Sliding window
• Need to record the character frequency of string t. While expanding the window, need to update the corresponding character frequency of the string s, and maintain the count of the needed characters. Maintaining the count of the needed characters can easily validate the current window by O(1).
• Details:
  • The template of sliding window, two while loops.
  • Keep expanding the window unless the character is needed.
  • Increment the count only if the character frequency in the current window is less than the needed frequency.
  • Move the right pointer before the second while loop.
  • Validate the current window and shrink the window in the second while loop.
  • Decrement the count only if the character frequency in the current window is equal to the needed frequency.
  • Move the left pointer after all the update/maintenance.
• Improvement:
  • Use int[128] to record the character frequency, the performance to validate the window is better than using a map.
  • Also can use int[58] (26 capital letters, 6 special characters, 26 lower case letters), but need to get the index by int[c - 'A'].
• Reference: https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/

Solution

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

        int[] need = new int[128];
        int[] have = new int[128];

        int left = 0;
        int right = 0;
        int min = Integer.MAX_VALUE;
        int start = 0;
        int count = 0;

        for(char c: t.toCharArray()){
            need[c]++;
        }

        while(right < s.length()){
            char r = s.charAt(right);

            if(need[r] == 0){
                right++;
                continue;
            }

            if(have[r] < need[r]){
                count++;
            }

            have[r]++;
            right++;

            while(count == t.length()){
                if(right - left < min){
                    min = right - left;
                    start = left;
                }

                char l = s.charAt(left);
                if(need[l] == 0){
                    left++;
                    continue;
                }

                if(have[l] == need[l]){
                    count--;
                }

                have[l]--;
                left++;
            }
        }
        return min < Integer.MAX_VALUE? s.substring(start, start + min): "";
    }
}

Complexity

• Time: O(m + n) m is the length of string s, n is the length of string t. Each character in string t is processed once. Each character in string s is processed once by right pointer, and once by left pointer.
• Space: O(1) the int[128].

[zhangzz2015]

思路

• 使用sliding window标准模板code。首先增加right，找到一个包含t的子串，为一个可行解，接一下增加left，找到最小满足条件的解。时间复杂度为O(n+m)，空间复杂度为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    string minWindow(string s, string t) {

        if(s.size()<t.size())
            return ""; 

        vector<int>  sMap(256,0); 
        vector<int>  tMap(256,0); 
        for(int i=0; i< t.size(); i++)
        {
            tMap[t[i]]++; 
        }
        int left =0; 
        int right =0; 
        int count =0; 
        int ret = INT_MAX; 
        int start = -1; 
        while(right < s.size())
        {
            int index = s[right]; 
            sMap[index]++; 
            if(sMap[index]<=tMap[index])
                count++; 
            while(count==t.size())
            {
                if(right-left+1<ret)
                {
                    ret = right - left+1; 
                    start = left; 
                }
                ret = min(ret, right - left+1); 
                int leftIndex = s[left]; 
                sMap[leftIndex]--; 
                if(sMap[leftIndex]<tMap[leftIndex])
                    count--; 
                left++; 
            }                        
            right++; 
        }

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

[Hacker90]

class Solution { public: string minWindow(string s, string t) { unordered_map<char,int>need,window; for(char c:t)need[c]++; string res; int len = INT_MAX; int start = 0; // int sLen = 0; int left = 0,right = 0,valid = 0; while(right<s.size()) { char a = s[right]; right++; if (need.count(a)) { window[a]++; if (window[a] == need[a])valid++; } while (valid == need.size()) { if (right - left < len ) { start = left; len = right - left; } 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);
}

};

[Toms-BigData]

【Day 46】76. 最小覆盖子串

思路

遍历T存到ｈａｓｈｍａｐ中，遍历S设置左右两指针ｌ，ｒ确定滑动窗口大小 ｒ先动，当ｓ［ｌ，ｒ］中的字符满足ｈａｓｈｍａｐ时，动ｌ，一直到不满足ｈａｓｈｍａｐ为止。 一直执行到最后，找出最短

golang代码

func minWindow(s string, t string) string {
    ori, cnt:= map[byte]int{}, map[byte]int{}
    for i := 0; i < len(t); i++ {
        ori[t[i]]++
    }
    sLen := len(s)
    length := math.MaxInt32
    ansL, ansR := -1, -1
    check := func() bool{
        for k, v := range ori{
            if cnt[k] < v{
                return false
            }
        }
        return true
    }
    for l, r:=0,0;r<sLen;r++{
        if r < sLen && ori[s[r]]>0{
            cnt[s[r]]++
        }
        for check()&&l<=r {
            if (r-l+1<length){
                length = r-l+1
                ansL,ansR = l, l+length
            }
            if _,ok := ori[s[l]];ok{
                cnt[s[l]] -= 1
            }
            l++
        }
    }
    if ansL == -1{
        return ""
    }
    return s[ansL:ansR]
}

复杂度

时间复杂度：最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。每次检查是否可行会遍历整个 t 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 C，则渐进时间复杂度为O(C⋅∣s∣+∣t∣)。 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 C ，则渐进空间复杂度为 O(C)。

[moirobinzhang]

Code:

public static string MinWindow(string s, string t) { if (t.Length > s.Length) return string.Empty;

        Dictionary<char, int> tDict = new Dictionary<char, int>();
        Dictionary<char, int> sDict = new Dictionary<char, int>();

        for (int i = 0; i < t.Length; i++)
        {
            if (!tDict.ContainsKey(t[i]))
                tDict.Add(t[i], 0);
            tDict[t[i]]++;
        }

        int minLen = Int32.MaxValue;
        string minStr = "";
        int cursorIndex = 0;
        int removeIndex = 0;

        for (; cursorIndex < s.Length; cursorIndex++)
        {
            if (!sDict.ContainsKey(s[cursorIndex]))
                sDict.Add(s[cursorIndex], 0);
            sDict[s[cursorIndex]]++;

            while (IsContains(sDict, tDict))
            {
                if (minLen > cursorIndex - removeIndex)
                {
                    minLen = cursorIndex - removeIndex;
                    minStr = s.Substring(removeIndex, minLen + 1);
                }

                sDict[s[removeIndex++]]--;
            }
        }

        return minStr;
    }

    public static bool IsContains(Dictionary<char, int> sDict, Dictionary<char, int> tDict)
    {
        if (sDict.Count < tDict.Count)
            return false;

        foreach (var item in tDict)
        {
            if (!sDict.ContainsKey(item.Key))
                return false;

            if (sDict[item.Key] < tDict[item.Key])
                return false;

        }

        return true;
    }

[xuhzyy]

思路

代码

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need, window = {}, {}
        for c in t:
            need[c] = need[c] + 1 if c in need else 1
            window[c] = 0

        l, r, valid = 0, 0, 0
        start, lenth = 0, float('inf')

        while(r < len(s)):
            c = s[r]
            if c in window:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1

            while(l <= r and valid == len(need)):
                if r - l + 1 < lenth:
                    start, lenth = l, r - l + 1

                d = s[l]
                if d in window:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

                l += 1

            r += 1

        return s[start:start+lenth] if lenth < float('inf') else ''

复杂度分析

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

[Tesla-1i]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        lookup = defaultdict(int)
        for c in t:
            lookup[c] += 1
        start, end = 0, 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

[ZJP1483469269]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n1 , n2 = len(s) , len(t)
        if n1 < n2 :
            return ''
        dic = {}
        cnt = 0
        for c in t:
            if c not in dic.keys():
                dic[c] = 0
                cnt += 1
            dic[c] += 1
        l = 0
        res = ''
        for r in range(n1):
            if s[r] in dic.keys():
                dic[s[r]] -= 1
                if dic[s[r]] == 0:
                    cnt -= 1
            while cnt == 0 and l <= r:
                if s[l] in dic.keys() and dic[s[l]] == 0:
                    res = s[l:r+1] if len(res) > r - l + 1 or len(res) == 0 else res
                if s[l] in dic.keys():
                    dic[s[l]] += 1
                    if dic[s[l]] > 0:
                        cnt += 1
                l += 1
        return res

[haixiaolu]

思路

滑动窗口

代码 / python

class Solution:
    def minWindow(self, str1: str, pattern: str) -> str:
        window_start, matched, substr_start = 0, 0, 0
        min_length = len(str1) + 1
        char_frequency = {}

        for chr in pattern:
            if chr not in char_frequency:
                char_frequency[chr] = 0
            char_frequency[chr] += 1

        # try to extend the range [window_start, window_end]
        for window_end in range(len(str1)):
            right_char = str1[window_end]
            if right_char in char_frequency:
                char_frequency[right_char] -= 1
                if char_frequency[right_char] >= 0:  # Count every matching of a character
                    matched += 1

            # Shrink the window if we can, finish as soon as we remove a matched character
            while matched == len(pattern):
                if min_length > window_end - window_start + 1:
                    min_length = window_end - window_start + 1
                    substr_start = window_start

                left_char = str1[window_start]
                window_start += 1
                if left_char in char_frequency:
                    # Note that we could have redundant matching characters, therefore we'll decrement the
                    # matched count only when a useful occurrence of a matched character is going out of the window
                    if char_frequency[left_char] == 0:
                        matched -= 1
                    char_frequency[left_char] += 1

        if min_length > len(str1):
            return ""
        return str1[substr_start:substr_start + min_length]

复杂度分析

• O (N + M)
• O (M)

[Flower-F]

解题思路

滑动窗口

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  const needMap = new Map();
  for (const ch of t) {
    needMap.set(ch, (needMap.get(ch) || 0) + 1);
  }

  let left = 0, right = 0;
  const storeMap = new Map();
  let start = 0, minLen = Number.MAX_SAFE_INTEGER;
  let valid = 0;

  while (right < s.length) {
    const ch = s[right];
    right++; // 移动右指针

    // 窗口数据更新
    if (needMap.has(ch)) {
      storeMap.set(ch, (storeMap.get(ch) || 0) + 1);
      if (storeMap.get(ch) === needMap.get(ch)) {
        // 当前窗口内字符数与需要的字符数相等
        valid++;
      }
    }

    // 判断左侧是否需要收缩
    while (valid === needMap.size) {
      // 进行答案的更新
      if (right - left < minLen) {
        minLen = right - left;
        start = left;
      }

      const ch = s[left];
      left++; // 移动左指针

      if (needMap.has(ch)) {
        // 如果相等，接下来进行减一操作之后，就不符合条件了
        if (storeMap.get(ch) === needMap.get(ch)) {
          valid--;
        }
        storeMap.set(ch, storeMap.get(ch) - 1);
      }
    }
  }

  return minLen === Number.MAX_SAFE_INTEGER ? '' : s.substr(start, minLen);
};

复杂度

时间：O(N + M) 空间：O(M)

[guoling0019]

Java Code:

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> hs = new HashMap<Character,Integer>();
        HashMap<Character,Integer> ht = new HashMap<Character,Integer>();
        for(int i = 0;i < t.length();i ++){
            ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        String ans = "";
        int len = 0x3f3f3f3f, cnt = 0; 
        for(int i = 0,j = 0;i < s.length();i ++)
        {
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++;
            while(j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j))))
            {
                int count = hs.get(s.charAt(j)) - 1;
                hs.put(s.charAt(j), count);
                j ++;
            }
            if(cnt == t.length() && i - j + 1 < len){
                len = i - j + 1;
                ans = s.substring(j,i + 1);
            }
        }
        return ans;
    }
}

[hdyhdy]

思路：滑动窗口

func minWindow(s string, t string) string {
    //题目给的条件
    if len(s) < len(t){
        return ""
    }
    //由于'z' - 'A'为57个，所以设为58
    out := ""
    var have [58]int
    var find [58]int
    valid := 0
    //记录当前窗口里面包含t中不同字符的个数
    cur := 0
    //循环记录t中不同字符的数量以及相同字符的出现的次数
    for i:=0;i<len(t);i++{
        if have[t[i]-'A'] == 0{
            valid++
        }
        have[t[i]-'A']++
    }

    //窗口大小[l...r]
    l,r := 0,-1
    //结束条件是左窗到最后
    for l < len(s){
        //如果r 还没有到最后面且此时的滑动窗口中出现的字符个数不够
        if (r+1)<len(s)&&valid != cur{
            //那就试着将r往后
            r++
            find[s[r]-'A']++
            if find[s[r]-'A'] == have[s[r]-'A']{
                cur++
            }
        }else{
            //如果r到头了或者此时的滑动窗口中出现的字符个数够了
            //那么就试着缩小窗口
            find[s[l]-'A']--
            if find[s[l]-'A'] == have[s[l]-'A']-1{
                cur--
            }
            l++
        }
        //如果此时滑动窗口中出现的字符个数够了
        //如果此时的out是空的或者out的长度比现在的答案长
        //更换答案
        if cur == valid{
            if out == ""|| len(out) > r-l+1{
                out = s[l:r+1]
            }
        }
    }
    return out
}

时间复杂度：O（n） 空间复杂度：O(c)

[linyang4]

思路

滑动窗口

1. 创建2个指针 left 和, right 默认都为 0
2. 向右移动 right 指针(扩大窗口), 直到 s[left, right] 中存在 t 的所有字符
3. 向右移动 left 指针(缩小窗口), 直到不满足条件, 记录下此时的 left 和 right, 作为备选答案
4. 重复 步骤2 和 步骤3, 不断更新最短的长度, 直到 right 指针移动到 s 的末尾

代码(JavaScript)

var minWindow = function(s, t) {
    if (s.length < t.length) { return '' }
    let left = right = valid = 0
    let minLeft, minRight // 用来标记最短子串的左右索引
    const targetMap = new Map()
    for(let i = 0; i < t.length; i++) {
        targetMap.set(t[i], (targetMap.get(t[i]) || 0) + 1)
    }
    const window = new Map()
    while(right < s.length) {
        const rightChar = s[right]
        let targetCount = targetMap.get(rightChar)
        right++
        if (targetCount !== undefined) {
            const curCount = (window.get(rightChar) || 0) + 1
            window.set(rightChar, curCount)
            if (curCount === targetCount) { valid++ }
        }

        // 收缩窗口
        while(valid === targetMap.size) {
            if (minLeft === undefined || (right - left) < (minRight - minLeft)) {
                minLeft = left
                minRight = right
            }
            const leftChar = s[left]
            targetCount = targetMap.get(leftChar)
            if(targetCount !== undefined) {
                const leftCount = window.get(leftChar) - 1
                window.set(leftChar, leftCount)
                if(leftCount === targetCount - 1) { valid-- }
            }
            left++
        }
    }
    return minLeft !== undefined ? s.slice(minLeft, minRight) : ''
}

复杂度

• 时间复杂度: O(s)
• 空间复杂度: O(t)

[callmeerika]

思路

滑动窗口

代码

  var minWindow = function (s, t) {
    const test = vv => {
      for (let value of vv.values()) {
        if (value > 0) {
          return false;
        }
      }
      return true;
    };
    let hash = new Map();
    let sn = s.length;
    let tn = t.length;
    for (let i = 0; i < tn; i++) {
      hash.set(t.charAt(i), (hash.get(t.charAt(i)) || 0) + 1);
    }
    let p = 0;
    let q = 0;
    let res = [0, Infinity];
    while (q < sn) {
      if (hash.get(s.charAt(q)) !== undefined) {
        hash.set(s.charAt(q), hash.get(s.charAt(q)) - 1);
      }
      while (test(hash) && p <= q) {
        if (q - p + 1 <= res[1] - res[0]) {
          res = [p, q];
        }
        if (hash.get(s.charAt(p)) !== undefined) {
          hash.set(s.charAt(p), hash.get(s.charAt(p)) + 1);
        }
        p++;
      }
      q++;
    }
    if (res[1] < Infinity) {
      return s.slice(res[0], res[1] + 1);
    }
    return '';
  };

复杂度

时间复杂度：O(m+n)
空间复杂度：O(m)

[xinhaoyi]

class Solution { public String minWindow(String s, String t) { if (s == null || s.length() == 0 || t == null || t.length() == 0){ return ""; } int[] need = new int[128]; //记录需要的字符的个数 for (int i = 0; i < t.length(); i++) { need[t.charAt(i)]++; } //l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0; //遍历所有字符 while (r < s.length()) { char c = s.charAt(r); if (need[c] > 0) {//需要字符c count--; } need[c]--;//把右边的字符加入窗口 if (count == 0) {//窗口中已经包含所有字符 while (l < r && need[s.charAt(l)] < 0) { need[s.charAt(l)]++;//释放右边移动出窗口的字符 l++;//指针右移 } if (r - l + 1 < size) {//不能右移时候挑战最小窗口大小，更新最小窗口开始的start size = r - l + 1; start = l;//记录下最小值时候的开始位置，最后返回覆盖串时候会用到 } //l向右移动后窗口肯定不能满足了 重新开始循环 need[s.charAt(l)]++; l++; count++; } r++; } return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size); } }

[JudyZhou95]

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:      
        need = collections.Counter(t)
        missing = len(t)

        i = 0
        I, J = 0, 0

        for j, c in enumerate(s):

            if c in need and need[c] > 0:
                missing -= 1

            need[c] -= 1

            if not missing:
                while i < j and need[s[i]] < 0:
                    need[s[i]] += 1
                    i += 1

                if not J or J-I > j-i:
                    I = i
                    J = j+1

        return s[I:J]

复杂度

TC: O(N+M) SC: O(M)

[LannyX]

思路

滑动

代码

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        if(n < m){
            return "";
        }
        Map<Character, Integer> map = new HashMap<>();

        for(char c : t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int min = Integer.MAX_VALUE, l = 0, r = 0, match = 0, resLeft = 0, resRight = 0;

        while(r < n){
            char ch = s.charAt(r);

            if(map.containsKey(ch)){
                int val = map.get(ch) - 1;
                if(val >= 0){
                    match++;
                }
                map.put(ch, val);
            }
            while(match == m){
                if(r - l + 1 < min){
                    min = r - l + 1;
                    resLeft = l;
                    resRight = r;
                }

                char chl = s.charAt(l);
                if(map.containsKey(chl)){
                    int val = map.get(chl) + 1;
                    if(val > 0){
                        match--;
                    }
                    map.put(chl, val);
                }
                l++;
            }
            r++;
        }
        return min == Integer.MAX_VALUE ? "" : s.substring(resLeft, resRight + 1);
    }
}

复杂度分析

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

[bigboom666]

代码

  public String minWindow(String s, String t) {
        if (s == null || t.length() == 0 || t == null || t.length() == 0) {
            return "";
        }
        int[] window = new int[128];
        for (int i = 0; i < t.length(); i++) {
            window[t.charAt(i)] += 1;
        }

        int right = 0, left = 0, count = t.length(), size = Integer.MAX_VALUE, start = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (window[c] > 0) {
                count--;
            }
            window[c] -= 1; 
            if (count == 0) {
                while (window[s.charAt(left)] < 0) {
                    window[s.charAt(left)]++;
                    left++;
                }
                if (right - left < size) {
                    size = right - left;
                    start = left;
                }
                window[s.charAt(left)]++;
                left++;
                count++;
            }
            right++; 
        }

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

[wxj783428795]

思路

• 滑动窗口 控制左右两个端点。
• 先向右移动右端点，直到左右端点之间的子串满足条件。
• 然后向右移动左端点，直到字串不满足条件（这一步是在找最短满足条件的子串）。
• 循环直到右端点到字符串末尾

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
    if (s.length < t.length) return '';
    let min = '';
    let tmap = new Map();
    for (let char of t) {
        if (tmap.has(char)) {
            tmap.set(char, tmap.get(char) - 1)
        } else {
            tmap.set(char, -1)
        }
    }
    let left = 0;
    let right = 1;
    let match = 0;
    while (left < right && right <= s.length) {
        let str = s.slice(left, right);
        char = str[str.length - 1];

        if (tmap.has(char)) {
            let val = tmap.get(char) + 1;
            if (val <= 0) {
                match++
            }
            tmap.set(char, val)
        }

        while (match === t.length) {
            str = s.slice(left, right);
            if (str.length < min.length || min === '') {
                min = str
            }
            let leftChar = s[left];
            if (tmap.has(leftChar)) {
                let val = tmap.get(leftChar) - 1;
                if (val < 0) {
                    match--;
                }
                tmap.set(leftChar, val)
            }
            left++
        }
        right++
    }
    return min;
};

复杂度

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

[zhiyuanpeng]

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

[ZhiweiZhen]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l = 0
        r = 0
        ans = None
        valid = 0
        backet = defaultdict(int)
        target = defaultdict(int)

        for i in t:
            target[i] += 1

        while r < len(s) or l < len(s):
            if r < len(s) and len(target) > valid:
                if s[r] in target:
                    backet[s[r]] += 1
                    if backet[s[r]] == target[s[r]]:
                        valid += 1
                r += 1

            else:
                if s[l] in backet:
                    backet[s[l]] -= 1
                    if backet[s[l]] + 1 == target[s[l]]:
                        valid -= 1
                l += 1

            if len(target) == valid:
                    if not ans or r - l < len(ans):
                        ans = s[l: r]

        return ans if ans else ''

[cszys888]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        need = defaultdict(int)
        needcnt = 0
        for c in t:
            need[c] += 1
            needcnt += 1

        res = [0, float('inf')]
        i = j = 0

        while j <= len(s) - 1:
            if s[j] in need:
                if need[s[j]] > 0:
                    needcnt -= 1
                need[s[j]] -= 1
            while needcnt != 0 and j <= len(s) - 2:
                j += 1
                if s[j] in need:
                    if need[s[j]] > 0:
                        needcnt -= 1
                    need[s[j]] -= 1
            if needcnt == 0:
            # now the window satisfy need, but not necessarily optimal
                while i <= len(s) - 1:
                    if s[i] not in need:
                        i += 1
                    elif need[s[i]] != 0:
                        need[s[i]] += 1
                        i += 1
                    else:
                        break

                # record candidate
                if j - i < res[1] - res[0]:
                    res[0], res[1] = i, j

            # move to new window
            need[s[i]] += 1
            needcnt += 1
            i += 1
            j += 1
        return "" if res[1] > len(s) else s[res[0]:(res[1]+1)]

time complexity: O(N+K), where N is the length of s, and K is the length of t space complexity: O(M), where M is the number of unique characters in t

[falconruo]

思路: 滑动窗口+哈希表

复杂度分析:

• 时间复杂度: O(N)
• 空间复杂度: O(1), 辅助数组freq(固定长度128)

代码(C++):

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";
        vector<int> freq(128);

        for (auto c : t)
            freq[c]++;

        int l = 0, cnt = 0;
        int minL = -1;
        int res = s.length() + 1;

        for (int i = 0; i < s.length(); i++) {
            freq[s[i]]--;

            if (freq[s[i]] >= 0) cnt++;

            while (cnt == t.length()) {
                if (res > i - l + 1) {
                    minL = l; 
                    res = i - l + 1;
                }
                freq[s[l]]++;
                if (freq[s[l]] > 0) cnt--;
                l++; // shrink left boarder
            }
        }

        return minL == -1 ? "" : s.substr(minL, res);   
    }
};

[pandaCure]

思路: 滑动窗口+哈希表

复杂度分析:

时间复杂度: O(N) 空间复杂度: O(1), 辅助数组freq(固定长度128) 代码(C++):

class Solution { public: string minWindow(string s, string t) { if (s.length() < t.length()) return ""; vector freq(128);

    for (auto c : t)
        freq[c]++;

    int l = 0, cnt = 0;
    int minL = -1;
    int res = s.length() + 1;

    for (int i = 0; i < s.length(); i++) {
        freq[s[i]]--;

        if (freq[s[i]] >= 0) cnt++;

        while (cnt == t.length()) {
            if (res > i - l + 1) {
                minL = l; 
                res = i - l + 1;
            }
            freq[s[l]]++;
            if (freq[s[l]] > 0) cnt--;
            l++; // shrink left boarder
        }
    }

    return minL == -1 ? "" : s.substr(minL, res);   
}

};

[kite-fly6618]

思路

滑动窗口

代码

var minWindow = function(s, t) {
    let res = '';
    let left = 0,right = 0;
    let needs = {};
    let windows = {};
    let match = 0,start = 0,minLen = Number.MAX_SAFE_INTEGER;
    for(let i = 0;i < t.length;i++){
        needs[t[i]] ? needs[t[i]]++ : needs[t[i]] = 1;
    }
    let needsLen = Object.keys(needs).length;
    while(right < s.length){
        let c1 = s[right];
        if(needs[c1]){
            windows[c1] ?  windows[c1]++ : windows[c1] = 1;
            if(windows[c1] === needs[c1]){
                match++;
            }
        }
        right++;
        while(match == needsLen){
            if(right - left < minLen){
               start = left;
               minLen = right - left; 
            }
            let c2 = s[left];
            if(needs[c2]){
                windows[c2]--;
                if(windows[c2] < needs[c2]){
                    match--;
                }

            }
            left++;
        }
    }
    return minLen === Number.MAX_SAFE_INTEGER ? '' : s.substr(start,minLen);
};

复杂度

时间复杂度：O(M+N)
空间复杂度：O(N)

[machuangmr]

代码

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        int sCnt = s.length();
        int tCnt = t.length();
        String ans = "";
        if(sCnt < tCnt) return ans;
        for(int i = 0;i < tCnt;i++) {
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int length = Integer.MAX_VALUE,  cnt = 0;
        for(int i = 0,j = 0;i < sCnt;i++) {
            sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
            if(tMap.containsKey(s.charAt(i)) && sMap.get(s.charAt(i)) <= tMap.get(s.charAt(i))) cnt++;
            while(j < i && (!tMap.containsKey(s.charAt(j))|| sMap.get(s.charAt(j)) > tMap.get(s.charAt(j)))){
                int count = sMap.get(s.charAt(j)) - 1;
                sMap.put(s.charAt(j), count);
                j++;
            }
            if(cnt == tCnt && i - j + 1 < length) {
                length = i - j + 1;
                ans = s.substring(j, i + 1);
            }
        }
        return ans;
    }
}

时间复杂度

• 时间复杂度 $O(n)$
• 空间复杂度 $O(n)$

[HWFrankFung]

Codes

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

[dahaiyidi]

Problem

76. 最小覆盖子串

++

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

---

Note

• 用need（大小为128）记录需要的字符的次数

• 怎么判断所找到的子串是否已经包含所有目标串？

  • 使用needcnt代表需要的字符的总数量
  • 当needcnt为

• 当找到字串s[l, r]中包含所需要的字符，下一步需要增加l，减少范围

• 注意：

  • 字符串经常用到哈希表
  • 字符串的操作要熟悉

---

Complexity

• 时间O：
• 空间O：

---

Python

C++

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> need(128, 0);
        for(auto& ch: t){
            need[ch] += 1;
        }
        int needCnt = t.size();

        int l = 0, r = 0, start = 0, size = INT_MAX;
        while(r < s.size()){
            // 若need[r]是所需要的字符
            if(need[s[r]] > 0){
                needCnt--;                
            }
            need[s[r]]--;

            // s[l, r]已经包含目标字符串，需要增大l，以减小长度
            if(needCnt == 0){
                while(1){
                    char ch = s[l];
                    if(need[ch] == 0){
                        // s[l]是必须的
                        break;
                    }
                    need[ch]++;
                    l++;
                }// 至此，[l,r]就是所需要的结果

                // 是否比现有的结果的长度短
                if(r - l + 1 < size){
                    size = r - l + 1;
                    start = l;
                }

                // 将l右移 
                need[s[l]]++; // 对应的位置+1
                l++; //右移
                needCnt++; // 需要的数量+1
            }
            r++;
        }
        return size < INT_MAX ? s.substr(start, size) : "";

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[Richard-LYF]

class Solution: def minWindow(self, s: str, t: str) -> str: ''' 如果hs哈希表中包含ht哈希表中的所有字符，并且对应的个数都不小于ht哈希表中各个字符的个数，那么说明当前的窗口是可行的，可行中的长度最短的滑动窗口就是答案。 ''' if len(s)<len(t): return "" hs, ht = defaultdict(int), defaultdict(int)#初始化新加入key的value为0 for char in t: ht[char] += 1 res = "" left, right = 0, 0 #滑动窗口 cnt = 0 #当前窗口中满足ht的字符个数

    while right<len(s):
        hs[s[right]] += 1
        if hs[s[right]] <= ht[s[right]]: #必须加入的元素
            cnt += 1 #遇到了一个新的字符先加进了hs，所以相等的情况cnt也+1
        while left<=right and hs[s[left]] > ht[s[left]]:#窗口内元素都符合，开始压缩窗口
            hs[s[left]] -= 1
            left += 1
        if cnt == len(t):
            if not res or right-left+1<len(res): #res为空或者遇到了更短的长度
                res = s[left:right+1]
        right += 1

    return res

    # on ok

[Myleswork]

思路

其实和昨天那题没什么太大的区别，无非今天这题是非定长滑动窗口，昨天那题是定长滑动窗口

之前的打卡题也有类似的，我记得是不大于sum的最短子串

代码

class Solution {
public:
    bool ist(string T,char t){
        for(char _t:T){if(_t==t) return true;}
        return false;
    }
    bool cmp(unordered_map<char,int>& hash1,unordered_map<char,int>& hash2){
        for(auto it = hash1.begin();it!=hash1.end();it++){
            if(hash2[it->first]<it->second) return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        int l = 0;
        string res = "";
        int slen = s.length();
        int tlen = t.length();
        unordered_map<char,int> hash1;
        unordered_map<char,int> hash2;
        for(char _t:t){
            hash1[_t]++;
            hash2.emplace(_t,0);
        }
        int minlen = s.length();
        for(int r = 0;r<slen;r++){
            if(r<tlen-1){
                if(ist(t,s[r])) hash2[s[r]]++;
                continue;
            }
            if(ist(t,s[r])) hash2[s[r]]++;
            while (cmp(hash1, hash2)) {
            if (ist(t, s[l])) hash2[s[l]]--;
            l++;
            if (r - l + 2 <= minlen) {
                minlen = r - l + 2;
                res = s.substr(l - 1, minlen);
            }
        }
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(slen)

空间复杂度：O(tlen)

[tongxw]

思路

不定长度滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length();
        int m = t.length();
        if (n < m) {
            return "";
        }

        Map<Character, Integer> countS = new HashMap<>();
        Map<Character, Integer> countT = new HashMap<>();
        for (int i=0; i<m; i++) {
            if (i != m - 1) {
                countS.put(s.charAt(i), countS.getOrDefault(s.charAt(i), 0) + 1);
            }
            countT.put(t.charAt(i), countT.getOrDefault(t.charAt(i), 0) + 1);
        }

        int minLen = Integer.MAX_VALUE;
        int start = -1;
        int end = -1;
        int l = 0;
        for (int r=m-1; r<n; r++) {
            countS.put(s.charAt(r), countS.getOrDefault(s.charAt(r), 0) + 1);
            while (exists(countT, countS)) {
                int len = r - l + 1;
                if (len < minLen) {
                    minLen = len;
                    start = l;
                    end = r;
                }

                countS.put(s.charAt(l), countS.getOrDefault(s.charAt(l), 0) - 1);
                l++;
            }
        }

        return start == -1 ? "" : s.substring(start, end+1);
    }

    private boolean exists(Map<Character, Integer> countT, Map<Character, Integer> countS) {
        for (char c : countT.keySet()) {
            if (countT.get(c) > countS.getOrDefault(c, 0)) {
                return false;
            }
        }

        return true;
    }
}

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

[alongchong]

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

[iambigchen]

思路

利用窗口大小不固定的滑动窗口模板。需要注意判断窗口内的字符串是否满足条件，利用两个map，一个用来存正确字符串的数量，另外一个存储窗口内字符串数量。

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let map1 = {}
    let map2 = {}
    for(let i = 0; i < t.length; i++) {
        map1[t[i]] = map1[t[i]] ? map1[t[i]] + 1 : 1
    }
    let l = 0
    let r = 0
    let min = +Infinity
    let matchNum = 0
    let start = 0
    let needsLen = Object.keys(map1).length;
    while(r < s.length) {
        let cur = s[r]
        if (map1[cur]) {
            map2[cur] = map2[cur] ? map2[cur]+1 : 1
            if (map2[cur] == map1[cur]) {
                matchNum++
            }
        }
        while(needsLen == matchNum) {
            if (min > r - l + 1) {
                min = r - l + 1
                start = l
            }
            let cur2 = s[l]
            if (map1[cur2]) {
                map2[cur2]--
                if (map2[cur2] < map1[cur2]) {
                    matchNum--
                }
            }
            l++
        }
        r++
    }
    return min == +Infinity ? '' : s.substr(start, min)
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(N+M)$
• 空间复杂度：$O(N)$

[Menglin-l]

approach: two pointers

---

code:

class Solution {
    public String minWindow(String source , String target) {
        // write your code here
        if (source == null || target == null || source.length() < target.length()) return "";

        int[] sourceArr = new int[128];
        int[] tarArr = new int[128];
        int numTar = 0;
        for (char c : target.toCharArray()) {
            tarArr[c] ++;
            if (tarArr[c] == 1) numTar ++;
        }

        int i = 0;
        int j = 0;
        int start = 0;
        int subLength = Integer.MAX_VALUE;
        int matchedChar = 0;
        while (i <= j && j < source.length()) {

            while (j < source.length() && matchedChar < numTar) {
                char a = source.charAt(j);
                sourceArr[a] ++;

                if (sourceArr[a] == tarArr[a]) matchedChar ++;

                j ++;
            }

            while (i <= j && matchedChar >= numTar) {
                if (subLength > j - i) {
                    subLength = j - i;
                    start = i;
                }
                char d = source.charAt(i);
                sourceArr[d]--;
                if (sourceArr[d] < tarArr[d]) matchedChar --;
                i ++;
            }
        }

        return subLength == Integer.MAX_VALUE ? "" : source.substring(start, start + subLength);
    }
}

---

complexity:

Time: O(N)

Space: O(1)

[testeducative]

思路：

滑动窗口

代码：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for(char c : t)
            need[c]++;
        int left = 0;
        int right = 0;
        int valid = 0;
        int len = INT_MAX;
        int start = 0;
        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 d = s[left];
                left++;
                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ?
                "" : s.substr(start, len);
    }
};

[spacker-343]

思路

只用统计target的词频，当满足target词频时，记录左右边界

代码

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
            need.put(c, 0);
        }
        int l = 0;
        int len = s.length();
        char[] cc = s.toCharArray();
        int cur = 0;
        int valid = map.size();
        int m = Integer.MAX_VALUE;
        int[] res = new int[2];
        for (int r = 0; r < len; r++) {
            if (need.containsKey(cc[r])) {
                need.put(cc[r], need.get(cc[r]) + 1);
                if (map.get(cc[r]).equals(need.get(cc[r]))) {
                    cur++;
                }
            }
            while (cur == valid && l <= r) {
                if (m > r - l + 1) {
                    m = r - l + 1;
                    res[0] = r;
                    res[1] = l;
                }
                char pre = cc[l];
                if (need.containsKey(pre)) {
                    need.put(pre, need.get(pre) - 1);
                    if (need.get(pre) < map.get(pre)) {
                        cur--;
                    }
                }
                l++;
            }
        }
        if  (m == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(res[1], res[0] + 1);
    }
}

复杂度

时间复杂度：O(n) 空间复杂度: O(1) 最多有26个字母