最小覆盖子串

题目描述：

给你一个字符串 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 由英文字母组成

思路:

用滑动窗口法来做

代码:

func minWindow(s string, t string) string {
    l,r := 0,0
    minl, minr := -1,-1
    lens := 999999
    m := make(map[byte]int, 0)
    cnt := make(map[byte]int, 0)
    var checked func() bool
    // 判断是不是字母都齐了
    checked = func() bool{
        for k,v := range m{
            if cnt[k] < v{
                return false
            }
        }
        return true
    }

    for i:=0; i<len(t); i++{
        m[t[i]] += 1
    }
    for  ;r <len(s) ;r++{
        if m[s[r]] >0{
            cnt[s[r]] ++
        }
        for checked() && l<=r{
            if r-l +1 <lens{
                lens = r-l+1
                minl, minr = l,l+lens
            }
            if _,ok := m[s[l]];ok{
                cnt[s[l]]--
            }
            l++
        }
    }
    if minl == -1{
        return ""
    }

    return s[minl:minr]
}

代码效率：

执行用时：108 ms, 在所有 Go 提交中击败了32.41%的用户
内存消耗：2.7 MB, 在所有 Go 提交中击败了98.09%的用户