题目

给定两个字符串 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.最小覆盖子串