leetcode-go/medium/395.longest-substring-with-at-least-k-repeating-characters.go

func longestSubstring(s string, k int) (max int) {
	freq, ban := make([]int, 256), make([]bool, 256)
	for _, r := range s {
		freq[r]++
	}
	cnt := 0
	for i := 'a'; i <= 'z'; i++ {
		if 0 < freq[i] && freq[i] < k {
			cnt++
			ban[i] = true
		}
	}
	n := len(s)
	if cnt == 0 { // No rune is forbidden, return n
		return n
	}
	beg := 0
	for i, r := range s {
		if ban[r] { // Split s into substrings using forbidden runes, then find the longest
			if k <= i-beg {
				max = maxInt(max, longestSubstring(s[beg:i], k))
			}
			beg = i + 1
		}
	}
	if k <= n-beg {
		max = maxInt(max, longestSubstring(s[beg:n], k))
	}
	return
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}