leetcode-go/hard/76.go

package main

func minWindow(s string, t string) string {
	m, n := len(s), len(t)
	if n == 0 {
		return ""
	}
	target, curr := make([]int, 256), make([]int, 256) // A little trick: byte < 256
	for i := 0; i < n; i++ {
		target[t[i]]++
	}
	cnt := 0
	left, right := -1, -1
	minLeft, minRight := -1, m-1
	for { // Create a slide window; all chars found, contract left; not enough, expand right.
		if cnt != n { // Expand right
			right++
			if right == m {
				break
			}
			if v := target[s[right]]; v > 0 {
				curr[s[right]]++
				if curr[s[right]] <= v {
					cnt++
				}
			}
		} else { // Contract left
			left++
			if v := target[s[left]]; v > 0 {
				curr[s[left]]--
				if curr[s[left]] < v {
					cnt--
					if right-left < minRight-minLeft {
						minLeft, minRight = left, right
					}
				}
			}
		}
	}
	if minLeft == -1 {
		return ""
	}
	return s[minLeft : minRight+1]
}

// func main() {
// 	println(minWindow("ADOBECODEBANC", "ABC"))
// 	println(minWindow("", "ABC"))
// 	println(minWindow("ADOBECODEBANC", ""))
// 	println(minWindow("ADOBECODEBANC", "CC"))
// }