📑 题目：76. 最小覆盖子串

🚀 本题 LeetCode 传送门

题目大意

给定一个源字符串 s，再给一个字符串 T，要求在源字符串中找到一个窗口，这个窗口包含由字符串各种排列组合组成的，窗口中可以包含 T 中没有的字符，如果存在多个，在结果中输出最小的窗口，如果找不到这样的窗口，输出空字符串。

解题思路

这一题是滑动窗口的题目，在窗口滑动的过程中不断的包含字符串 T，直到完全包含字符串 T 的字符以后，记下左右窗口的位置和窗口大小。每次都不断更新这个符合条件的窗口和窗口大小的最小值。最后输出结果即可。

代码

package leetcode
func minWindow(s string, t string) string {
 if s == "" || t == "" {
  return ""
 }
 var tFreq, sFreq [256]int
 result, left, right, finalLeft, finalRight, minW, count := "", 0, -1, -1, -1, len(s)+1, 0
 for i := 0; i < len(t); i++ {
  tFreq[t[i]-'a']++
 }
 for left < len(s) {
  if right+1 < len(s) && count < len(t) {
   sFreq[s[right+1]-'a']++
   if sFreq[s[right+1]-'a'] <= tFreq[s[right+1]-'a'] {
    count++
   }
   right++
  } else {
   if right-left+1 < minW && count == len(t) {
    minW = right - left + 1
    finalLeft = left
    finalRight = right
   }
   if sFreq[s[left]-'a'] == tFreq[s[left]-'a'] {
    count--
   }
   sFreq[s[left]-'a']--
   left++
  }
 }
 if finalLeft != -1 {
  result = string(s[finalLeft : finalRight+1])
 }
 return result
}