leetcode-pp / 91alg-5-daily-check

91 天学算法第五期打卡

55 stars 14 forks source link

【Day 46 】2021-10-25 - 76. 最小覆盖子串 #63

Open azl397985856 opened 3 years ago

azl397985856 commented 3 years ago

76. 最小覆盖子串

入选理由

暂无

题目地址

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

前置知识

Sliding Window

哈希表

题目描述


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

示例：

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

提示：

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

yanglr commented 3 years ago

思路:

这题与昨天打卡的 438. 找到字符串中所有字母异位词的解法有点像。

方法: 滑动窗口 + 哈希表

在字符串s中维护一个滑动窗口, 窗口有start 和end两个指针。每次去判断start和end范围内的窗口所包含的substring有没有包含t中的所有字符。

如果当前窗口子串包含t中的所有字符且更短, 就更新result。

代码:

实现语言: C++

注: 扩展ASCII码(EXTENDED_ASCII)字符集包含256个字符，大写A的ASCII码是65, 小写z的ASCII码是122。所以, 用数组模拟哈希表时, 大小用256足够了。

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> tMap(256); // 字符串t中的字母频次表, 用数组模拟哈希表
        for (int i=0; i < t.size(); i++)
            tMap[t[i]]++;
        int count = t.size();  // 待匹配的字符的数量
        vector<int> sMap(256); // 滑动窗口中的字母频次表, 用数组模拟哈希表
        int left = -1; // 记录结束时滑动窗口的start、end
        int right = -1;
        int start = 0;
        int minLen = INT_MAX;
        for (int i = 0; i < s.size(); i++) /* 循环变量i即为滑动窗口的end */
        {
            char ch = s[i];
            sMap[ch]++;
            if (sMap[ch] <= tMap[ch]) /* 匹配上了一个待匹配字符, 待匹配字符的数量可以-1 */
                count--;
            while (start <= i && count == 0) /* start需要满足边界条件, 如果当前窗口恰好包含字符串t中所有的字符, 需要移动指针试试看有没有更短的 */
            {
                char h = s[start];
                sMap[h]--; /* 从滑动窗口丢掉一个字符串s中此时start位置的字符h(head), 如果发现sMap中字符h的数量不够了, 则待匹配字符才数量+1 */
                if (sMap[h] < tMap[h]) count++;
                if (count > 0) /* 此时start还没移动, count出现第一次>0 的位置即表示出现新的符合题意的窗口 */
                {
                    if (minLen > i - start + 1)  /* 如果出现更短的窗口, 更新一下相关数据 */
                    {
                        left = start;
                        right = i;
                        minLen = right - left + 1;
                    }
                }
                start++;
            }                
        }
        if (left == -1) return "";
        return s.substr(left, right - left + 1);
    }
};

复杂度分析

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

for123s commented 3 years ago

思路

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    int query_idx(char c)
    {
        if(c>='a'&&c<='z')
            return c-'a';
        return c-'A'+26;
    }
    string minWindow(string s, string t) {
        if(s.size()<t.size())
            return {};
        vector<int> c_t(52,0);
        for(int i=0;i<t.size();i++)
            c_t[query_idx(t[i])]++;
        string res=s+'a';
        int l=0, r=0;
        vector<int> c_s(52,0);
        int len_ = 0;
        while(r<s.size())
        {
            int idx_r = query_idx(s[r]);
            c_s[idx_r]++;
            if(c_s[idx_r]<=c_t[idx_r])
            {
                len_++;
                while(len_==t.size())
                {
                    if(r-l+1<res.size())
                        res = s.substr(l,r-l+1);
                    int idx_l = query_idx(s[l]);
                    c_s[idx_l]--;
                    if(c_s[idx_l]<c_t[idx_l])
                        len_--;
                    ++l;
                }
            }
            ++r;
        }
        if(res.size()==s.size()+1)
            return {};
        return res;
    }
};

复杂度分析

令 n 为数组长度。

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

zhangzz2015 commented 3 years ago

思路

滑动窗口是处理没有顺序要求字符串匹配的利器，记录t中每个字符出现次数。通过滑动窗口遍历s，先移动右边界，如果在s中出现则增加 count，注意有重复字符，同一个字符最大出现的次数不能超过s中的最大次数。当count和 s 字符串大小相同，则表面已经包含s 中所有的字符，为了找到最小包含关系，此时移动左边界，直到count 小于s字符串大小。再移动右边，重复整个过程。时间复杂度为O(N)，空间复杂度为O(1)。

关键点

代码

语言支持：C++

C++ Code:


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

        vector<int> trecord(256,0); 
        vector<int> srecord(256,0); 

        for(int i =0; i< t.size(); i++)
        {
            trecord[t[i]]++; 
        }

        int left =0; 
        int right =0; 
        int count =0; 
        string ret; 
        int retIndex = INT_MAX; 
        while(right<s.size())
        {
            int index = s[right] ; 
            srecord[index]++; 
            if(trecord[index]> 0 && srecord[index]<=trecord[index])
            {
                count++; 
            }

            // shink window
            while(count == t.size())
            {
                if((right-left+1)<retIndex)
                {
                    retIndex = right - left+1; 
                    ret = s.substr(left, retIndex); 
                }
                int leftIndex = s[left] ; 
                srecord[leftIndex]--; 
                if(srecord[leftIndex]<trecord[leftIndex])
                {
                    count--; 
                }
                left++; 
            }
            right++;    
        }

        return ret; 
    }
};

Menglin-l commented 3 years ago

思路：

1. 用长度为128的数组记录字符出现的次数

2. 滑窗

代码部分：

class Solution {
    public String minWindow(String s, String t) {
    int[] map = new int[128];

    for (char ch : t.toCharArray()) map[ch] ++;

    int tLen = t.length();
    int left = 0;
    int right = 0;

    int win = Integer.MAX_VALUE;
    int str = 0; // t开始的位置
    while (right < s.length()) {
        if (map[s.charAt(right ++)] -- > 0) tLen --;

        // 如果全覆盖
        while (tLen == 0) {
            // 更新更小的窗口
            if (right - left < win) {
                win = right - left;
                str = left;
            }

            if (map[s.charAt(left ++)] ++ == 0) tLen ++;
        }
    }

        if (win != Integer.MAX_VALUE) return s.substring(str, str + win);

        return "";
    }
}

复杂度：

Time: O(N)

Space: O(1)

yachtcoder commented 3 years ago

Sliding window.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l, counter, N, ct = 0, Counter(), len(s), Counter(t)
        k = 0
        ret, rs = 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:
                    rs = 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 rs

wangzehan123 commented 3 years ago

题目地址(76. 最小覆盖子串)

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

题目描述

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

 

注意：

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

 

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

 

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

 

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

前置知识

公司

暂无

思路

关键点

代码

语言支持：Java

Java Code:


class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        //维护两个数组，记录已有字符串指定字符的出现次数，和目标字符串指定字符的出现次数
        //ASCII表总长128
        int[] need = new int[128];
        int[] have = new int[128];

        //将目标字符串指定字符的出现次数记录
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }

        //分别为左指针，右指针，最小长度(初始值为一定不可达到的长度)
        //已有字符串中目标字符串指定字符的出现总频次以及最小覆盖子串在原字符串中的起始位置
        int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0;
        while (right < s.length()) {
            char r = s.charAt(right);
            //说明该字符不被目标字符串需要，此时有两种情况
            // 1.循环刚开始，那么直接移动右指针即可，不需要做多余判断
            // 2.循环已经开始一段时间，此处又有两种情况
            //  2.1 上一次条件不满足，已有字符串指定字符出现次数不满足目标字符串指定字符出现次数，那么此时
            //      如果该字符还不被目标字符串需要，就不需要进行多余判断，右指针移动即可
            //  2.2 左指针已经移动完毕，那么此时就相当于循环刚开始，同理直接移动右指针
            if (need[r] == 0) {
                right++;
                continue;
            }
            //当且仅当已有字符串目标字符出现的次数小于目标字符串字符的出现次数时，count才会+1
            //是为了后续能直接判断已有字符串是否已经包含了目标字符串的所有字符，不需要挨个比对字符出现的次数
            if (have[r] < need[r]) {
                count++;
            }
            //已有字符串中目标字符出现的次数+1
            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;
                }
                //如果左边即将要去掉的字符被目标字符串需要，且出现的频次正好等于指定频次，那么如果去掉了这个字符，
                //就不满足覆盖子串的条件，此时要破坏循环条件跳出循环，即控制目标字符串指定字符的出现总频次(count）-1
                if (have[l] == need[l]) {
                    count--;
                }
                //已有字符串中目标字符出现的次数-1
                have[l]--;
                //移动左指针
                left++;
            }
        }
        //如果最小长度还为初始值，说明没有符合条件的子串
        if (min == s.length() + 1) {
            return "";
        }
        //返回的为以记录的起始位置为起点，记录的最短长度为距离的指定字符串中截取的子串
        return s.substring(start, start + min);
    }
}

复杂度分析

令 n 为数组长度。

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

cicihou commented 3 years ago


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        '''
        sliding window
        '''
        target = Counter(t)

        if len(s) < len(t) or len(set(s)) < len(set(t)) or set(s).intersection(set(t)) != set(t):
            return ''

        l = r = 0
        tmp = {}
        res = ''

        required_count = len(t)

        while r < len(s):
            if s[r] in target:
                tmp[s[r]] = tmp.get(s[r], 0) + 1
                if tmp[s[r]] <= target[s[r]]:
                    required_count -= 1

            while required_count == 0:
                if s[l] in tmp:
                    if len(res) == 0 or len(s[l:r+1]) < len(res):
                        res = s[l:r+1]
                    tmp[s[l]] -= 1
                    if tmp[s[l]] < target[s[l]]:
                        required_count += 1
                    if tmp[s[l]] == 0:
                        tmp.pop(s[l])
                l += 1
            r += 1
        return res

chang-you commented 3 years ago

//T:O(n)

class Solution {
    public String minWindow(String s, String t) {
        int[] count = new int[256];
        for (char c : t.toCharArray()) {
            count[c]++;
        }

        int len = t.length();
        int min = Integer.MAX_VALUE;
        int from = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (count[s.charAt(i)]-- > 0) {
                len--;
            }
            while (len == 0) {
                if (i - j + 1 < min) {
                    min = i - j + 1;
                    from = j;
                }
                if (++count[s.charAt(j++)] > 0) {
                    len++;
                }
            }
        }
        return (min == Integer.MAX_VALUE) ? "" : s.substring(from, from + min);
    }
}

xieyj17 commented 3 years ago

from collections import Counter
class Solution:    
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""
        def is_insde(s, t):
            for i in t.keys():
                if (i not in s) or (s[i] < t[i]):
                    return False
            return True
        t_dict = Counter(t)
        w_dict = Counter(s[0:len(t)])
        res = ""
        if is_insde(w_dict, t_dict):
            res = s[0:len(t)]
        left = 0
        right = len(t)    
        while right < len(s):
            while not is_insde(w_dict, t_dict) and right < len(s):
                if s[right] not in w_dict:
                    w_dict[s[right]] = 1
                else:
                    w_dict[s[right]] += 1
                right += 1

            while is_insde(w_dict, t_dict) and left < right:
                if len(res) == 0:
                    res = s[left:right]
                elif len(res) > (right - left):
                    res = s[left:right]
                if w_dict[s[left]] > 1:
                    w_dict[s[left]] -= 1
                else:
                    del w_dict[s[left]]
                left += 1

        return res

Expand the right end of rolling window until it contains the target t
Shrink the left end until the rolling window no longer contains the target
Compare the length of the rolling window with existing ans, update ans if it's shorter

Time: O(N)

Space: O(len(t))

nonevsnull commented 3 years ago

思路

拿到题的直觉解法
- 可以直接套用双指针模版，for套while，比较map即可，这样的方式思路最清楚，用来锻炼模版很好，但是复杂度有点高；
- 可以进一步优化一下map的比较使得复杂度降低，但需要修改模版

AC

代码

//模版直接套用
class Solution {
    public String minWindow(String s, String t) {
        int left = 0;
        int[] res = {0, Integer.MAX_VALUE};
        HashMap<Character, Integer> map = new HashMap<>();
        HashMap<Character, Integer> source = new HashMap<>();

        for(int i = 0;i < t.length();i++){
            char cur = t.charAt(i);
            source.putIfAbsent(cur, 0);
            source.put(cur, source.get(cur)+1);
        }

        for(int i = 0;i < s.length();i++){
            char cur = s.charAt(i);
            map.putIfAbsent(cur, 0);
            map.put(cur, map.get(cur)+1);

            while(included(map, source)){
                if(i - left < res[1] - res[0]){
                    res[0] = left;
                    res[1] = i;
                }
                char leftChar = s.charAt(left);
                left++;
                map.put(leftChar, map.get(leftChar)-1);
            }
        }

        return res[1] == Integer.MAX_VALUE?"":s.substring(res[0], res[1]+1);
    }

    public boolean included(HashMap<Character, Integer> map, HashMap<Character, Integer> source){
        for(char key: source.keySet()){
            if(!map.containsKey(key) || map.get(key) < source.get(key)){
                return false;
            }
        }

        return true;
    }
}
//优化比较map
class Solution {
    public String minWindow(String s, String t) {
        int left = 0, budget = 0;
        int[] res = {0, Integer.MAX_VALUE};
        HashMap<Character, Integer> map = new HashMap<>();

        for(int i = 0;i < t.length();i++){
            char cur = t.charAt(i);
            map.putIfAbsent(cur, 0);
            map.put(cur, map.get(cur)+1);
            budget++;
        }

        for(int i = 0;i < s.length();i++){
            char cur = s.charAt(i);
            if(map.containsKey(cur)){
                int latest = map.get(cur);
                if(latest > 0) budget--;
                map.put(cur, map.get(cur) - 1);
            }

            while(budget <= 0){
                if(i - left < res[1] - res[0]){
                    res[0] = left;
                    res[1] = i;
                }
                char leftC = s.charAt(left);
                if(map.containsKey(leftC)){
                    map.put(leftC, map.get(leftC) + 1);
                    if(map.get(leftC) > 0) budget++;
                }
                left++;
            }
        }

        return res[1] == Integer.MAX_VALUE?"":s.substring(res[0], res[1]+1);
    }

}

复杂度

//直接套用模版 time: O(mn) space: O(m+n)

//优化 time: O(n+m) space:O(n)

yingliucreates commented 3 years ago

link:

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

代码 Javascript

const minimumWindowSubstring = function (string, substring) {
  let answer = ""

  let map = {}
  substring.split("").forEach((character) => (map[character] = (map[character] || 0) + 1))
  let count = Object.keys(map).length

  let left = 0
  let right = -1

  while (right < string.length) {
    if (count === 0) {
      if (!answer || right - left + 1 < answer.length) {
        answer = string.slice(left, right + 1)
      }

      if (map[string[left]] !== undefined) {
        map[string[left]]++
      }
      if (map[string[left]] > 0) {
        count++
      }
      left++
    } else {

      right++
      if (map[string[right]] !== undefined) {
        map[string[right]]--
      }
      if (map[string[right]] === 0) {
        count--
      }
    }
  }
  return answer
}

pophy commented 3 years ago

思路

滑动窗口，窗口边界为l, r
构建countMap，用来统计窗口中，每个字符需要的个数
r向右滑动，直到满足条件（每个t中的字符都出现，包括重复）
- 记录当前窗口str，l向右移动收缩窗口，直到不满足条件
使用变量needCount记录当前窗口是否满足条件避免每次窗口改变都需要检查所有字符

Java Code

    public String minWindow(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return "";
        }
        Map<Character, Integer> countMap = new HashMap<>();
        int neededCount = 0;
        for (char c : t.toCharArray()) {
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
            neededCount++;
        }
        int l = 0, r = 0, minLength = Integer.MAX_VALUE;
        String str = "";
        while (r < m) {
            while (neededCount != 0 && r < m) {
                char c = s.charAt(r);
                if (countMap.containsKey(c)) {
                    if (countMap.get(c) > 0) {
                        neededCount--;
                    }
                    countMap.put(c, countMap.get(c) - 1);
                }
                r++;
            }
            while (l < m && neededCount == 0) {
                if (r - l < minLength) {
                    minLength = r- l;
                    str = s.substring(l, r);
                }
                char c = s.charAt(l);
                if (countMap.containsKey(c)) {
                    countMap.put(c, countMap.get(c) + 1);
                    if (countMap.get(c) > 0) {
                        neededCount++;
                    }
                }
                l++;
            }
        }
        return str;
    }

时间&空间

时间 O(n)
空间 O(n)

Yufanzh commented 3 years ago

Intuition

Sliding window problem

Algorithm in python3

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(s) < len(t):
            return ""
        need_dict = collections.defaultdict(int)
        for char in t:
            need_dict[char] += 1

        window_dict = collections.defaultdict(int)
        # sliding window two pointers
        left = right = 0
        # count when substring find all character in t
        match = 0

        #index to record final result
        start = 0
        end = 100010

        # start to increase window
        while right < len(s):
            c = s[right]
            right += 1
            if c in need_dict:
                window_dict[c] += 1
                if window_dict[c] == need_dict[c]:
                    match += 1

            # start to shrink when match reaches to len(need_dict)
            while match == len(need_dict):
                #update start and end index
                if right - left < end - start:
                    start = left
                    end = right
                d = s[left]
                if d in need_dict:
                    if window_dict[d] == need_dict[d]:
                        match -= 1
                    window_dict[d] -= 1
                left += 1

        if end == 100010:
            return ""
        else:
            return s[start : end]

Complexity Analysis

Time complexity: O(N)
Space complexity: O(N)

shuichen17 commented 3 years ago

/*Time complexity: O(S + T)
  Space complexity: O(S + T)
*/
var minWindow = function(s, t) {
    let left = 0;
    let map = new Map();
    let count = t.length;
    let minLen = Number.MAX_VALUE;
    let res = "";
    for (let ele of t) {
        if (!map.has(ele)) {
            map.set(ele , 1);
        } else {
            map.set(ele, map.get(ele) + 1);
        }
    }
    for (let i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
           if (map.get(s[i]) > 0) {
               count--;
           }
            map.set(s[i], map.get(s[i]) - 1);
        }        
        while (count === 0) {        
            if (minLen > (i - left + 1)) {                 
                minLen = i - left + 1;              
                res = s.substr(left, minLen);
            }
            if (map.has(s[left])) {
                map.set(s[left], map.get(s[left]) + 1);
                if (map.get(s[left]) > 0) {
                    count++;
                }
            }
            left++;
        }
    }
    return res;    
};

HackBL commented 3 years ago

class Solution {
    public String minWindow(String s, String t) {
    int[] map = new int[128];

    for (char ch : t.toCharArray()) map[ch] ++;

    int tLen = t.length();
    int left = 0;
    int right = 0;

    int win = Integer.MAX_VALUE;
    int str = 0; // t开始的位置
    while (right < s.length()) {
        if (map[s.charAt(right ++)] -- > 0) tLen --;

        // 如果全覆盖
        while (tLen == 0) {
            // 更新更小的窗口
            if (right - left < win) {
                win = right - left;
                str = left;
            }

            if (map[s.charAt(left ++)] ++ == 0) tLen ++;
        }
    }

        if (win != Integer.MAX_VALUE) return s.substring(str, str + win);

        return "";
    }
}

tongxw commented 3 years ago

思路

非固定长度滑动窗口。首先右指针遍历数组。如果左右指针内的窗口包含目标字符串，那么右指针暂停前进，此时如果窗口长度小于之前的最小长度，那么更新最小长度和左右指针位置，并收缩左指针，直到窗口内不包含字符串为止。然后再移动右指针。如何判断窗口内是否包含目标字符串：哈希表计数，然后对比。由于字符串只包含大小写字母，可以用长度为52的整型数组代替哈希表。

代码

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

        int[] charsInT = new int[52]; // SC O(1)
        countChars(t, 0, n-1, charsInT, false); // O(n)

        int[] charsWindow = new int[52];
        countChars(s, 0, n-2, charsWindow, false); // O(n)

        int ansStart = -1;
        int ansEnd = -1;
        int minLen = Integer.MAX_VALUE;
        int left = 0;
        for (int right = n-1; right < m; right++) { // O(m)
            countChars(s, right, right, charsWindow, false); // O(1)
            while( exists(charsInT, charsWindow) ) { // O(1)
                if (minLen > right - left + 1) {
                    minLen = right - left + 1;
                    ansStart = left;
                    ansEnd = right;
                }

                // move forward the left boundry
                countChars(s, left, left, charsWindow, true); // O(1)
                left++;
            }
        }

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

    }

    private void countChars(String str, int start, int end, int[] count, boolean decrease) {
        for (int i=start; i<=end; i++) {
            char c = str.charAt(i);
            if (Character.isLowerCase(c)) {
                count[c - 'a'] += decrease ? -1 : 1;
            } else if (Character.isUpperCase(c)) {
                count[c - 'A' + 26] += decrease ? -1 : 1;
            }
        }
    }

    private boolean exists(int[] lookupChars, int[] windowChars) {
        for (int i=0; i<lookupChars.length; i++) {
            if (windowChars[i] < lookupChars[i]) {
                return false;
            }
        }

        return true;
    }
}

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

fzzfgbw commented 3 years ago

思路

滑动窗口

代码

func minWindow(s string, t string) string {
    minl:=0
    minr:= len(s)
    l, r := 0, 0
    count:=0
    memo := make([]int, 124)
    for i := range t {
        memo[t[i]]++
        count++
    }
    for r < len(s) {
        if memo[s[r]]>0 {
            count--
        }
        memo[s[r]]--
        for l<=r &&  count==0 {
            if r-l<minr-minl {
                minl,minr = l,r
            }
            if memo[s[l]]>=0 {
                count++
            }

            memo[s[l]]++
            l++
        }
        r++
    }
    if minr!=len(s) {
        return s[minl:minr+1]
    }else {
        return ""
    }
}

复杂度分析

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

Laurence-try commented 3 years ago

思路

官方题解

代码

使用语言：Python3

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        # Dictionary which keeps a count of all the unique characters in t.
        dict_t = Counter(t)

        # Number of unique characters in t, which need to be present in the desired window.
        required = len(dict_t)

        # left and right pointer
        l, r = 0, 0

        # formed is used to keep track of how many unique characters in t are present in the current window in its desired frequency.
        # e.g. if t is "AABC" then the window must have two A's, one B and one C. Thus formed would be = 3 when all these conditions are met.
        formed = 0

        # Dictionary which keeps a count of all the unique characters in the current window.
        window_counts = {}

        # ans tuple of the form (window length, left, right)
        ans = float("inf"), None, None

        while r < len(s):

            # Add one character from the right to the window
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            # If the frequency of the current character added equals to the desired count in t then increment the formed count by 1.
            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            # Try and contract the window till the point where it ceases to be 'desirable'.
            while l <= r and formed == required:
                character = s[l]

                # Save the smallest window until now.
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                # The character at the position pointed by the `left` pointer is no longer a part of the window.
                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                # Move the left pointer ahead, this would help to look for a new window.
                l += 1    

            # Keep expanding the window once we are done contracting.
            r += 1    
        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]

复杂度分析 时间复杂度：O(n+k) 空间复杂度：O(s)

ZacheryCao commented 3 years ago

Idea:

Sliding window. Increase right side till the substring has all chars in the string t, then increase left side until one char of the string t has fewer frequency than it should be in current substring.

Code

from collections import Counter
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_count = Counter(t)
        desired = len(t_count)
        k = 0
        s_count = Counter()
        length, start, end = math.inf, 0, 0
        i = 0
        for j in range(len(s)):
            if s[j] in t_count:
                s_count[s[j]] = s_count.get(s[j], 0) + 1
                if s_count[s[j]] == t_count[s[j]]:
                    k += 1
            while desired == k:
                if j - i + 1 < length:
                    length = j - i + 1
                    start, end = i, j
                if s[i] in s_count:
                    if s_count[s[i]] == t_count[s[i]]:
                        k -= 1
                    s_count[s[i]] -= 1
                i += 1
        return s[start:end+1] if length != math.inf else ""

Compelxity:

Time: O(N + M). N: the length of string s. M: the length of string t. We scan though string t to get the frequency of the chars. The scan twice of string s in worst case, once for the left side, once for the right side. Space: o(1). Since s, t only contains lowercase and uppercase letters. In the worst case it will be 52, and the container for frequency will be 78.

falconruo commented 3 years ago

思路: 使用双指针l, i来表示滑动窗口的左右边界，使用哈希表freq来记录给定字符串t中的字母出现的次数

复杂度分析:

时间复杂度: O(N), 其中N为字符串s和字符串t的长度之和(n + m)
空间复杂度: O(1), 辅助数组freq(固定长度128)

代码(C++):

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

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

        int l = 0, minLeft = -1, cnt = 0, 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) {
                    res = i - l + 1;
                    minLeft = l;
                }

                freq[s[l]]++; 
                if (freq[s[l]] > 0) cnt--;

                l++;
            }
        }

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

mmboxmm commented 3 years ago

思路

滑动窗口

代码

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

        int[] map = new int[256];
        int cnt = 0;
        for (char c : t.toCharArray()) {
            map[c]++;
            if (map[c] == 1) {
                cnt++;
            }
        }

        char[] src = s.toCharArray();
        int start = 0, end = 0;
        int rStart = 0, rEnd = src.length;

        for (end = 0; end < src.length; end++) {
            map[src[end]]--;

            if (map[src[end]] == 0) {
                cnt--;
            }

            if (cnt == 0) {
                while (map[src[start]]++ < 0) {
                    start++;
                }

                if (end - start < rEnd - rStart) {
                    rStart = start;
                    rEnd = end;
                }

                start++;
                cnt++;
            }
        }

        return rEnd == src.length ? "" : s.substring(rStart, rEnd + 1);   
    }
}

复杂度

Time: O(n)

siyuelee commented 3 years ago

class Solution(object):
    def minWindow(self, s, t):
        l = r = 0
        target = Counter(t)
        target_cnt = len(target.keys())
        res = ''

        while r < len(s):
            if s[r] in target:
                target[s[r]] -= 1
                if target[s[r]] == 0:
                    target_cnt -= 1

            while target_cnt == 0 and l <= r:
                if len(res) == 0 or len(s[l:r+1]) < len(res):
                    res = s[l:r+1] 
                if s[l] in target:
                    target[s[l]] += 1
                    if target[s[l]] > 0:
                        target_cnt += 1
                l += 1
            r += 1
        return res

T: n S: n

kidexp commented 3 years ago

thoughts

滑动窗口 + hashmap

这里需要两个hashmap 一个存需要的char的数目，一个存window里面的char的数目

还需要一个变量计数，和needed的长度比较，是不是已经满足了，

这个变量只有当window里面的char对应的count和needed里面对应的count一样的时候才会+1或者减一

code

from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(t) > len(s):
            return ""
        needed_map, window_map = defaultdict(int), defaultdict(int)
        left = valid_count = 0
        min_left = min_right = -1
        for char in t:
            needed_map[char] += 1
        for i, char in enumerate(s):
            if char in needed_map:
                window_map[char] += 1
                if window_map[char] == needed_map[char]:
                    valid_count += 1
            while valid_count == len(needed_map):
                if min_left == -1 or i - left + 1 <= min_right - min_left:
                    min_left, min_right = left, i+1
                if s[left] in needed_map:
                    if window_map[s[left]] == needed_map[s[left]]:
                        valid_count -= 1
                    window_map[s[left]] -= 1
                left += 1
        return s[min_left:min_right]

Complexity

m == s.length, n == t.length

时间复杂度 O(m+n)

空间复杂度 O(n)

qyw-wqy commented 3 years ago

public String minWindow(String s, String t) {
        int[] count = new int[128];
        int unique = 0;
        for (char c : t.toCharArray()) {
            if (count[c]++ == 0) unique++;
        }

        int start = -1;
        int len = Integer.MAX_VALUE;
        for (int l = 0, r = 0; r < s.length(); r++) {
            if (count[s.charAt(r)]-- == 1) unique--;
            while (unique == 0) {
                if (r - l + 1 < len) {
                    start = l;
                    len = r - l + 1;
                }  
                if (count[s.charAt(l++)]++ == 0) unique++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

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

kennyxcao commented 3 years ago

76. Minimum Window Substring

Intuition

Sliding Window + Character Frequency Counter
Maintain the minimum sliding window in s that includes all the chars in t.

Code

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
const minWindow = function(s, t) {
  const targetFreq = getCharFreq(t);
  const windowFreq = {};
  let matches = 0; // match count of target chars within current window
  let start = 0;
  let minStart = 0;
  let minWidth = Infinity;
  for (let i = 0; i < s.length; i++) {
    windowFreq[s[i]] = (windowFreq[s[i]] || 0) + 1;
    if (windowFreq[s[i]] <= (targetFreq[s[i]] || 0)) {
      matches += 1;
    }
    if (matches === t.length) {
      while (windowFreq[s[start]] > (targetFreq[s[start]] || 0)) {
        windowFreq[s[start++]] -= 1;
      }
      if (minWidth > i - start + 1) {
        minWidth = i - start + 1;
        minStart = start;
      }
    }
  }
  return minWidth === Infinity ? '' : s.substr(minStart, minWidth);
};

function getCharFreq(str) {
  const charFreq = {};
  for (const char of str) {
    charFreq[char] = (charFreq[char] || 0) + 1;
  }
  return charFreq;
}

Complexity Analysis

Time: O(m + n)
Space: O(m + n)
m = len(s)
n = len(t)

joeytor commented 3 years ago

思路

使用滑动窗口模板方法, 每次先向右移动窗口, 直到能够符合要求向左收缩窗口直到不符合要求, 并在其中更新状态信息

所以先右移窗口知道所有 t 中的字符都在窗口内, 直到符合要求

然后持续左移窗口, 并且每次更新, 直到不符合要求

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

        left, right = 0, 0
        valid = 0

        count_dict = {key:0 for key in t}
        target_dict = {}
        for char in t:
            target_dict[char] = target_dict.get(char, 0) + 1

        min_left, min_length = 0, 1e9

        while right < len(s):

            c = s[right]
            if c in count_dict:
                count_dict[c] += 1
                if count_dict[c] == target_dict[c]:
                    valid += 1

            right += 1

            while valid == len(target_dict):

                if right - left < min_length:
                    min_length = right - left
                    min_left = left

                c1 = s[left]

                if c1 in count_dict:
                    count_dict[c1] -= 1
                    if count_dict[c1] < target_dict[c1]:
                        valid -= 1

                left += 1

        if min_length == 1e9:
            return ""
        else:
            return s[min_left: min_left + min_length]

复杂度

n 为 s 的长度, m 为 t 的长度

时间复杂度: O(n+m) 因为两个指针每个 s 中字符最多访问一次, t 是 count 的时候遍历了一次

空间复杂度: O(m) count 的结果存储的空间复杂度是 O(m)

yan0327 commented 3 years ago

思路：写完昨天的每日一题，刚刚好回去总结了一下双指针。本质这题是滑动窗口 + 包含该字串【满足条件后收缩】+寻找最小字串。最：说明找到一个最小的r-l+1 针对这种有限的字母，或字符串，可以用一个数组来代替哈希表。小写字母为26，大小字母为58. 这题还是不能一遍AC，记得只有在cur == count 的情况才，才有必要对out与当前窗进行判断！！！最后要注意边界条件！！！

func minWindow(s string, t string) string {
    have := [58]int{}
    want := [58]int{}
    count := 0
    cur := 0
    out := ""
    if len(s) < len(t){
        return out
    }
    for _,x := range t{
        if want[x-'A'] == 0{
            count++
        }
        want[x-'A']++
    }
    l,r := 0,-1
    for l < len(s){
        if r <len(s)-1&&cur != count{
            r++
            have[s[r]-'A']++
            if want[s[r]-'A'] == have[s[r]-'A']{
                cur++
            }
        }else{
            have[s[l]-'A']--
            if have[s[l]-'A'] < want[s[l]-'A']{
                cur--
            }
            l++
        }
        if cur == count{
            if out == "" || len(out) > r-l+1{
                out = s[l:r+1]
        }
        }

    }
    return out
}

时间复杂度：O（m+n）空间复杂度:O(1)

Shinnost commented 3 years ago

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        words = defaultdict(int)
        for i in t:
            words[i] += 1
        #初始化
        left = 0
        right = 0
        ns = len(s)
        nt = len(t)
        n = 0
        result = ''
        #保证起始位置有效
        while right < ns and words[s[right]] == 0:
           left += 1
           right += 1

        while right < ns:
            #仅当left和right位置都是有效字符时才进行判断
            if s[right] in t:
                words[s[right]] -= 1
                if words[s[right]] >= 0:
                    n += 1 #用于统计是否已满足条件
                #缩小窗口，去除左端冗余
                while words[s[left]] < 0:
                    words[s[left]] += 1
                    left += 1
                    #保证left处于有效字符位
                    while s[left] not in t:
                        left += 1
                if n == nt and (result == '' or len(result) > right - left + 1):
                    result = s[left:right + 1]

            right += 1

        return result

heyqz commented 3 years ago

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""

        d = {}
        for c in t:
            d[c] = d.get(c, 0) + 1
        require = len(d)

        window = {}
        l, r = 0, 0
        ans = [float('inf'), 0, 0]
        have = 0

        while r < len(s):
            window[s[r]] = window.get(s[r], 0) + 1 

            if s[r] in d and window[s[r]] == d[s[r]]:
                have += 1

            while l <= r and have == require:
                if r - l + 1 < ans[0]:
                    ans = [r-l+1, l, r]

                window[s[l]] -= 1 
                if s[l] in d and window[s[l]] < d[s[l]]:
                    have -= 1

                l += 1 

            r += 1

        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

time complexity: O(m+n) space complexity: O(n)

ghost commented 3 years ago

题目

Minimum Window Substring

思路

Sliding window + Hash Table

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        memo = collections.defaultdict(int)
        res = ''
        length = len(s) + len(t)
        rest = 0

        for char in t:
            memo[char] += 1
            rest += 1

        l = r = 0

        while(r < len(s)):
            if s[r] in memo:
                if memo[s[r]] > 0:
                    rest-=1 
                memo[s[r]] -= 1

            while(rest == 0):   
                if r-l+1 < length:
                    res = s[l:r+1]
                    length = r-l+1
                if s[l] in memo:
                    if memo[s[l]] >= 0:
                        rest+=1
                    memo[s[l]]+=1
                l += 1
            r+=1

        return res

复杂度

Space: O(len(t)) Time: O(len(s)+len(t))

septasset commented 3 years ago

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

}

thinkfurther commented 3 years ago

思路

使用滑动窗口寻找最小

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        import collections
        t_len = len(t)
        matched_chars = 0
        t_dict = collections.Counter(t)
        currentLength = float('inf')
        currentPos = [0,0]
        slow = 0
        for fast in range(len(s)):
            fast_char = s[fast]
            if fast_char in t_dict:
                t_dict[fast_char] -= 1
                if t_dict[fast_char] >= 0:
                    matched_chars += 1

            while (matched_chars == t_len):
                if (fast - slow + 1 < currentLength):
                    currentLength = fast - slow + 1
                    currentPos = [slow, fast]

                slow_char = s[slow]
                if slow_char in t_dict:
                    t_dict[slow_char] += 1
                    if t_dict[slow_char] > 0:
                        matched_chars -= 1
                slow += 1

        if currentLength == float('inf'):
            return ""
        else:
            return s[currentPos[0] : currentPos[1] + 1]

复杂度

时间复杂度：O(N+K)

空间复杂度：O(S)

wangyifan2018 commented 3 years ago

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int)
        for c in t:
            need[c]+=1
        needCnt=len(t)
        i=0
        res=(0,float('inf'))
        for j,c in enumerate(s):
            if need[c]>0:
                needCnt-=1
            need[c]-=1
            if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[i] 
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                if j-i<res[1]-res[0]:   #记录结果
                    res=(i,j)
                need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1
                i+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

james20141606 commented 3 years ago

Day 46: 76. Minimum Window Substring (sliding window, string)

Problem Link
- 76. Minimum Window Substring
Ideas
- We use sliding window, to add chars at right and shrink chars at the left when we meet a new char at the coming right which is the same with the current left. (implementing this is a bit tricky). We have target_len and reduce it when we add a new char at right if it is in t. Only when it is 0 we consider updating left. so each time we update the left we need to add back one for the current left char.
Complexity: hash table and bucket
- Time: O(len(t) + len(s))
- Space: O(len(t))
Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)            #hash table to store char frequency
        #print (need)
        missing = len(t)                         #total number of chars we care
        start, end = 0, 0
        min_len = len(s)
        i = 0
        for j, char in enumerate(s, 1):          #index j from 1
            #print ('1',need,  s[i], j, i)
            if need[char] > 0:       #for char in t, we decrease missing
                missing -= 1
            need[char] -= 1

            if missing == 0:                     #match all chars
                while i + len(t) < j and need[s[i]] < 0:  #remove chars to shrink 
                    #print ('1',need,  s[i], j, i)
                    need[s[i]] += 1
                    i += 1
                #print (need,  s[i], j, i)
                need[s[i]] += 1                  #make sure the first appearing char satisfies need[char]>0
                missing += 1                     #we missed this first char, so add missing by 1
                if j - i <= min_len:  #update window
                    start, end = i, j
                    min_len = j-i
                i += 1                           #update i to start+1 for next window
            #print (need)
        return s[start:end]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        counter_t = Counter(t)
        #keys_t = set(t)
        #counter_cur = {key: 0 for key in keys_t}
        #print (counter_t, counter_cur)
        target_len = len(t)
        left = 0
        start, end = 0, 0
        min_len = len(s)
        #while right, and then while left to shrink, update target_len until it is 0
        for right, char in enumerate(s, 1):          #index j from 1 but char from beginning
            #print (counter_t)
            if counter_t[char] > 0:  #for char in t, we decrease target length
                #print ('counter_t[char]', counter_t[char], right)
                target_len -= 1         
            counter_t[char] -= 1  #if negative means we have redundancy, we do not need some chars (either in t or not in t!), then we could shrink the left
            #print ('target_len', target_len)
            if target_len == 0:   #we already have all the chars, but may have even more redundant chars, so then we go into the process to update left
                #print (left + len(t) < right, counter_t[s[left]])
                while left + len(t) < right and counter_t[s[left]] < 0: #remove chars to shrink, note for counter_t[s[left]], the char in t is already 0, so left will stop exactly at the char needed in t
                    print ('s', s[left], left, right)
                    counter_t[s[left]] += 1
                    left += 1
                #print (counter_t,  s[left], right, left)
                counter_t[s[left]] += 1 #these two lines are tricky, it is very important, it will add 1 to the left position's corresponding char which is needed in t
                target_len += 1 #it ensures that not all the right in the for loop will go to shrink step, only when the right position is a char in t which is just the left position's char will leads shrink!
                # for example in "ADOBECODEBANC" "ABC"; we already have "ADOBEC", then we have another B, that will not lead to shrink since we need A to shrink, so the above two lines could make this work
                if right - left <= min_len:
                    min_len = right - left
                    start, end = left, right
                left += 1 #we still need to update left for the next window!
                #print ('start, end', start, end)
        return s[start:end]

other resources:

florenzliu commented 3 years ago

Explanation

first, use a hashmap to count the letters in t
sliding window on the string s
- keep a hashmap of the sliding window
- keep the count of required letters in t (required) and the count of already matched letters in s (formed)
- in each step, update the current window and check if the conditions are satisfied
- then move the left pointer to move forward until the conditions are not satisfied again

Python

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

        d = defaultdict(int)
        for ch in t:
            d[ch] += 1

        window = defaultdict(int)
        start = 0
        minValue = math.inf
        pos = -1
        formed, required = 0, len(d)
        for i in range(len(s)):
            curr = s[i]
            window[curr] += 1
            if curr in d and window[curr] == d[curr]:
                formed += 1
            while start <= i and formed == required:
                if minValue > i - start + 1:
                    minValue = i - start + 1
                    pos = start
                window[s[start]] -= 1
                if s[start] in d and window[s[start]] < d[s[start]]:
                    formed -= 1
                start += 1

        return s[pos: pos+minValue] if pos != -1 else ""

Complexity:

Time Complexity: O(m + n) where m is the length of s and n is the length of t
Space Complexity: O(m + n)

xueniuniu98 commented 3 years ago

思路：如果hs(用来包含ht的)哈希表中包含ht哈希表中的所有字符，并且对应的个数都不小于ht哈希表中各个字符的个数，那么说明当前的窗口是可行的，可行中的长度最短的滑动窗口就是答案。 class Solution: def minWindow(self, s: str, t: str) -> str: if len(s)<len(t): return ""
hs = defaultdict(int) #初始化key的value为0，不能用hs = {}，后面hs[s[right]] += 1要累加
ht = Counter(t) 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 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

xj-yan commented 3 years ago

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> patternMap = new HashMap<>();
        for (char c : t.toCharArray()){
            patternMap.put(c, patternMap.getOrDefault(c, 0) + 1);
        }

        String res = s + " ";
        int leftBound = 0, count = patternMap.size();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (!patternMap.containsKey(c)) continue;
            patternMap.put(c, patternMap.get(c) - 1);
            if (patternMap.get(c) == 0) count--;
            while (count == 0){
                if (i - leftBound + 1 < res.length()){
                    res = s.substring(leftBound, i + 1);
                }
                char leftChar = s.charAt(leftBound++);
                if (!patternMap.containsKey(leftChar)) continue;
                patternMap.put(leftChar, patternMap.get(leftChar) + 1);
                if (patternMap.get(leftChar) > 0) count++;
            }
        }

        return res.length() == s.length() + 1 ? "" : res;
    }
}

Time Complexity: O(m + n), Space Complexity: O(n)

st2yang commented 3 years ago

思路

滑动窗口
counter

代码

python

class Solution:
def minWindow(self, s: str, t: str) -> str:
    if not s and not t:
        return ""
    n = len(s)

    cnt_t = collections.Counter(t)
    required = len(cnt_t)
    formed = 0 # condition: formed == required

    curr = collections.defaultdict(int) # store curr count
    res = s + s
    l = 0

    for r in range(n):
        r_char = s[r]
        if r_char in cnt_t:
            curr[r_char] += 1
            if curr[r_char] == cnt_t[r_char]:
                formed += 1

        while formed == required and l <= r:
            if r - l + 1 < len(res):
                res = s[l:r+1]

            l_char = s[l]
            if l_char in cnt_t:
                curr[l_char] -= 1
                if curr[l_char] < cnt_t[l_char]:
                    formed -= 1

            l += 1

    if len(res) == 2 * len(s):
        return ""
    return res

复杂度

时间: O(n_s)
空间: O(1)

chun1hao commented 3 years ago

var minWindow = function (s, t) {
  let map = new Map();
  for (let i of t) {
    map.set(i, (map.get(i) || 0) + 1);
  }
  let size = map.size;
  let tempMap = new Map();
  let curSize = 0;
  let ans = s + "-";
  let j = 0;
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      let num = tempMap.get(s[i]) || 0;
      tempMap.set(s[i], ++num);
      if (num === map.get(s[i])) curSize++;
      while (curSize === size) {
        if (i - j + 1 < ans.length) {
          ans = s.slice(j, i + 1);
        }
        if (tempMap.has(s[j])) {
          let count = tempMap.get(s[j]) - 1;
          tempMap.set(s[j], count);
          if (count < map.get(s[j])) curSize--;
        }
        j++;
      }
    }
  }
  return ans.length > s.length ? "" : ans;
};

freesan44 commented 3 years ago

思路

滑动窗口，右边扩张，满足字符串遍历条件后，左边收缩，难点在于左边收缩的边界条件

代码

语言支持：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)$

wenlong201807 commented 3 years ago

代码块


var minWindow = function (s, t) {
  // 需要的
  let need = {};
  // 窗口中的字符
  let window = {};
  for (let a of t) {
    // 统计需要的字符
    need[a] = (need[a] || 0) + 1;
  }
  // 左右指针
  let left = 0,
    right = 0;
  let valid = 0;
  // 最小覆盖子串的起始索引及长度
  let start = 0,
    len = Number.MAX_VALUE;
  while (right < s.length) {
    // 即将移入窗口的字符
    let c = s[right];
    // 右移窗口
    right++;
    if (need[c]) {
      // 当前字符在需要的字符中，则更新当前窗口统计
      window[c] = (window[c] || 0) + 1;
      if (window[c] == need[c]) {
        // 当前窗口和需要的字符匹配时，验证数量增加1
        valid++;
      }
    }
    // 当验证数量与需要的字符个数一致时，就应该收缩窗口了
    while (valid == Object.keys(need).length) {
      // 更新最小覆盖子串
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      //即将移出窗口的字符
      let d = s[left];
      // 左移窗口
      left++;
      if (need[d]) {
        if (window[d] == need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return len == Number.MAX_VALUE ? '' : s.substr(start, len);
};

时间复杂度和空间复杂度

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

JK1452470209 commented 3 years ago

思路

一直往右边进行试探匹配到t个字符时，左侧开始收缩。滑动窗口大小不固定，收缩到边界时记录left与right下标。

代码

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

复杂度

时间复杂度：O(N)

空间复杂度：O(T)

xyinghe commented 3 years ago

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

flame0409 commented 3 years ago

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> patternMap = new HashMap<>();
        for (char c : t.toCharArray()){
            patternMap.put(c, patternMap.getOrDefault(c, 0) + 1);
        }

        String res = s + " ";
        int leftBound = 0, count = patternMap.size();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (!patternMap.containsKey(c)) continue;
            patternMap.put(c, patternMap.get(c) - 1);
            if (patternMap.get(c) == 0) count--;
            while (count == 0){
                if (i - leftBound + 1 < res.length()){
                    res = s.substring(leftBound, i + 1);
                }
                char leftChar = s.charAt(leftBound++);
                if (!patternMap.containsKey(leftChar)) continue;
                patternMap.put(leftChar, patternMap.get(leftChar) + 1);
                if (patternMap.get(leftChar) > 0) count++;
            }
        }

        return res.length() == s.length() + 1 ? "" : res;
    }
}

hewenyi666 commented 3 years ago

题目名称

76. 最小覆盖子串

题目链接

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

题目思路

滑动窗口 + 双指针解法

code for Python3

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        words = defaultdict(int)
        for i in t:
            words[i] += 1
        #初始化
        left = 0
        right = 0
        ns = len(s)
        nt = len(t)
        n = 0
        result = ''
        #保证起始位置有效
        while right < ns and words[s[right]] == 0:
           left += 1
           right += 1

        while right < ns:
            #仅当left和right位置都是有效字符时才进行判断
            if s[right] in t:
                words[s[right]] -= 1
                if words[s[right]] >= 0:
                    n += 1 #用于统计是否已满足条件
                #缩小窗口，去除左端冗余
                while words[s[left]] < 0:
                    words[s[left]] += 1
                    left += 1
                    #保证left处于有效字符位
                    while s[left] not in t:
                        left += 1
                if n == nt and (result == '' or len(result) > right - left + 1):
                    result = s[left:right + 1]

            right += 1

        return result

复杂度分析

时间复杂度: O(N)
空间复杂度: O(N)

shamworld commented 3 years ago

var minWindow = function(s, t) {
    let l=0;
    let r=0;
    let map=new Map();
  for(let c of t){
    map.set(c,map.has(c)?map.get(c)+1:1)
  }
  let maptype=map.size;
  let res='';
    while(r<s.length){
        const c=s[r];
        if(map.has(c)){
            map.set(c,map.get(c)-1)
            if(map.get(c)===0){
                maptype -=1
            }
        }
        while(maptype===0){
            const newres=s.substring(l,r+1);
            if(!res||res.length>newres.length) res=newres;
            const c2=s[l];
            if(map.has(c2)){
                map.set(c2,map.get(c2)+1);
                if(map.get(c2)===1){
                    maptype +=1;
                }

            }
            l +=1
        }
        r+=1
    }
    return  res

};

biancaone commented 3 years ago

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ''

        remaining_counter = collections.Counter(t)
        valid_count = 0
        left, min_len = 0, sys.maxsize
        left_start = 0

        for right in range(len(s)):
            if s[right] in remaining_counter:
                if remaining_counter[s[right]] > 0:
                    valid_count += 1
                remaining_counter[s[right]] -= 1

            while valid_count == len(t):
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    left_start = left

                if s[left] in remaining_counter:
                    remaining_counter[s[left]] += 1
                    if remaining_counter[s[left]] > 0:
                        valid_count -= 1

                left += 1

        if min_len == sys.maxsize:
            return ''

        return s[left_start: left_start + min_len]

xjlgod commented 3 years ago

class Solution {

    public String minWindow(String s, String t) {
       int sLen = s.length();
       int tLen = t.length();
       if (sLen < tLen) {
           return "";
       }
       // window当中需要匹配的字符
       Map<Character, Integer> need = new HashMap<>();
       for (int i = 0; i < t.length(); i++) {
           need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
       }
       // 还有多少个字符未被匹配
       int needCount = t.length();
       int len = Integer.MAX_VALUE;
       int left = 0, right = 0, start = 0, end = 0;
       while (right < sLen) {
           char key = s.charAt(right);
           // 和匹配字符相关，进行判断
           if (need.containsKey(key)) {
               if (need.get(key) > 0) {
                   needCount--;
               }
           }
           need.put(key, need.getOrDefault(key, 0) - 1);
           // 成功匹配，开始缩减窗口
           if (needCount == 0) {
               // 窗口开始缩减，直到缩减到必须字符位置
               while (need.get(s.charAt(left)) != 0) {
                   need.put(s.charAt(left), need.get(s.charAt(left)) + 1);
                   left++;
               }   
               int temp = right - left + 1;
               if (temp < len) {
                   len = temp;
                   start = left;
                   end = right;
               }
               need.put(s.charAt(left), need.get(s.charAt(left)) + 1);
               needCount++;
               left++;
           }
           right++;
       }
       if (len == Integer.MAX_VALUE) {
           return "";
       }
       return s.substring(start, end + 1);

    }

}

akxuan commented 3 years ago

思路

滑动窗口 + hash 这题其实不难, 关键还是边界条件不好做. 尽量做到 onepass 总结window的模板

时间复杂度: n 空间: n

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

        if len(t) == 0:
            return ""

        cnt_t = collections.Counter(t)
        cnt_s = collections.Counter([])

        l,r = 0 ,0

        cnt_t_len  = len(t)
        cnt_s_len  = 0

        min_win = float('inf')
        res = ''
        while  r < len(s)+1 and l<=r:

            if len(cnt_s) < len(cnt_t) and r < len(s):
                cnt_s.update(s[r])
                r+=1

            else:
                if r< len(s) and  len(cnt_t - cnt_s) >0:
                        cnt_s.update(s[r])
                        r +=1

                elif len(cnt_t - cnt_s) ==0:

                        if min_win > r-l+1:
                            min_win = r-l+1 
                            res = s[l:r]

                        cnt_s[s[l]] -=1
                        l +=1
                else:

                    l +=1

        return res

jaysonss commented 3 years ago

思路

用哈希表记录下t的字符频率，并用一个cnt变量表示当前的匹配程度，cnt==0代表匹配，cnt>0代表不匹配
滑动窗口，不断更新哈希表和cnt，当取到结果后缩小左边界直到取到最小子集(cnt>0)

代码

class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer> tMap = new HashMap<>();
        int cnt = t.length();
        for(char tc: t.toCharArray()){
            rightNext(tc, tMap);
        }
        int[] ans = new int[]{0,Integer.MAX_VALUE};
        int left =0, right = 0;

        while(right < s.length()){
            int count = tMap.getOrDefault(s.charAt(right),0);
            if(count > 0){
                cnt--;
            }
            leftNext(s.charAt(right),tMap);

            if(cnt == 0){
                while(cnt == 0){
                    char leftC = s.charAt(left);
                    int leftCharCount = tMap.getOrDefault(leftC,Integer.MIN_VALUE);
                    if(leftCharCount == 0){
                        cnt++;
                    }

                    rightNext(leftC,tMap);
                    left++;
                }

                if(right - left + 1 < ans[1]-ans[0]){
                    ans[0] = left-1;
                    ans[1] = right;
                }
            }
            right++;
        }
        return ans[1] == Integer.MAX_VALUE ? "" : s.substring(ans[0], ans[1]+1);       
    }

    void leftNext(char c,Map<Character,Integer> windowMap){
        windowMap.put(c,windowMap.getOrDefault(c,0)-1);
    }

    void rightNext(char c,Map<Character,Integer> windowMap){
        windowMap.putIfAbsent(c,0);
        windowMap.put(c,windowMap.get(c)+1);

    }
}

时间复杂度： O(s.length)
空间复杂度：O(s.length + t.length)