题目

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

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

解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：输入：s = "a", t = "a" 输出："a"

示例 3：输入：s = "a", t = "aa" 输出：""

解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：1 <= s.length, t.length <= 105

s 和 t 由英文字母组成

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

注意：本题与主站 76 题相似（本题答案不唯一）：

解题思路分析

1、滑动窗口；时间复杂度O(n^2)，空间复杂度O(n)

func minWindow(s string, t string) string {   if len(s) < len(t) {      return ""   }   window := make(map[byte]int)   need := make(map[byte]int)   for i := 0; i < len(t); i++ {      need[t[i]]++   }   left, right := -1, -1   minLength := math.MaxInt32   for l, r := 0, 0; r < len(s); r++ {      if r < len(s) && need[s[r]] > 0 {         window[s[r]]++      }      // 找到，然后left往右移      for check(need, window) == true && l <= r {         if r-l+1 < minLength {            minLength = r - l + 1            left, right = l, r+1         }         if _, ok := need[s[l]]; ok {            window[s[l]]--         }         l++      }   }   if left == -1 {      return ""   }   return s[left:right]}func check(need, window map[byte]int) bool {   for k, v := range need {      if window[k] < v {         return false      }   }   return true}

2、滑动窗口；时间复杂度O(n)，空间复杂度O(n)

func minWindow(s string, t string) string {   if len(s) < len(t) {      return ""   }   arr := make(map[byte]int)   for i := 0; i < len(t); i++ {      arr[t[i]]++   }   l, count := 0, 0   res := ""   minLength := math.MaxInt32   for r := 0; r < len(s); r++ {      arr[s[r]]--      if arr[s[r]] >= 0 {         count++      }      // left往右边移动      for count == len(t) {         if minLength > r-l+1 {            minLength = r - l + 1            res = s[l : r+1]         }         arr[s[l]]++         if arr[s[l]] > 0 {            count--         }         l++      }   }   return res}

Hard题目，题目同leetcode 76.最小覆盖子串