最小覆盖子串 - 滑动窗口
func minWindow(s string, t string) string {
sLen, tLen := len(s), len(t)
if sLen < tLen {
return ""
}
// idx: char
// val: 欠款多少
mp := [58]int{}
debt := 0 // 欠款总数
for i := 0; i < tLen; i++ {
mp[t[i] - 'A']++
debt++
}
left := 0
start := 0
length := math.MaxInt
for right := 0; right < sLen; right++ {
mp[s[right] - 'A']-- // 还款
if mp[s[right] - 'A'] >= 0 { // 有效还款
debt--
}
if debt == 0 { // 还清
for mp[s[left] - 'A'] < 0 { // 拿回无效还款
mp[s[left] - 'A']++
left++
}
l := right - left + 1
if l < length {
length = l
start = left
}
// 继续向右看是否有更小的覆盖子串
mp[s[left] - 'A']++
left++
debt = 1
}
}
if length == math.MaxInt {
return ""
}
return s[start:start + length]
}