LC76 - 最小覆盖子串

package Substring

import "math"

func minWindow(s string, t string) string {
    hashMap := make(map[byte]int)
    debt := 0
    for i := 0; i < len(t); i++ {
        hashMap[t[i]]--
        debt++
    }
    minLen := math.MaxInt
    minPos := 0
    for lbound, rbound := 0, 0; rbound < len(s); rbound++ {
        if hashMap[s[rbound]] < 0 {
            debt--
        }
        hashMap[s[rbound]]++
        if debt == 0 {
            for ; hashMap[s[lbound]] > 0; lbound++ {
                hashMap[s[lbound]]--
            }
            if rbound-lbound+1 < minLen {
                minLen = rbound - lbound + 1
                minPos = lbound
            }
        }
    }
    if minLen == math.MaxInt {
        return ""
    }
    return s[minPos : minPos+minLen]
}

debt变量记录总债务，hashMap记录具体的债务表。第一阶段滑动窗口不断扩大，直至总债务减小为0。第二阶段滑动窗口每次扩大一格(右边界向右移动)，随后尝试缩小(左边界向右移动)。