leetcode-go/leetcode/medium/567.permutation-in-string.go

func checkInclusion(s1 string, s2 string) bool {
	m, n := len(s1), len(s2)
	if n < m {
		return false
	}
	freq := make([]int, 256)
	for _, r := range s1 {
		freq[r]++
	}
	beg, end := 0, -1
	cnt := make([]int, 256)
	for end < n {
		for beg = end + 1; beg < n && freq[s2[beg]] == 0; beg++ {
		}
		copy(cnt, freq)
		for end = beg; end < n; end++ {
			ch := s2[end]
			if freq[ch] == 0 {
				break
			}
			cnt[ch]--
			for cnt[ch] < 0 {
				cnt[s2[beg]]++
				beg++
			}
			if isEmpty(cnt) {
				return true
			}
		}
	}
	if isEmpty(cnt) {
		return true
	}
	return false
}

func isEmpty(cnt []int) bool {
	for i := 'a'; i <= 'z'; i++ {
		if cnt[i] != 0 {
			return false
		}
	}
	return true
}