leetcode-go/leetcode/medium/424.longest-repeating-character-replacement.go

type SegmentTree struct {
	tree []int
	size int
}

func newST(n int) SegmentTree {
	return SegmentTree{
		tree: make([]int, 2*n),
		size: n,
	}
}

func (st SegmentTree) add(i, val int) {
	i += st.size
	st.tree[i] += val
	for 1 < i {
		j := i / 2
		st.tree[j] = maxInt(st.tree[2*j], st.tree[2*j+1])
		i = j
	}
}

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

func characterReplacement(s string, k int) (max int) {
	n := len(s)
	if n-1 <= k {
		return n
	}
	bytes := []byte(s)
	st := newST(26)
	fast, slow, cnt := 0, 0, 0
	for ; fast < n; fast++ {
		st.add(int(bytes[fast]-'A'), 1)
		cnt = st.tree[1]
		for cnt+k < fast-slow+1 {
			st.add(int(bytes[slow]-'A'), -1)
			slow++
			cnt = st.tree[1]
		}
		max = maxInt(max, fast-slow+1)
	}
	return
}