// Package q1888 implements a solution for https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/
package q1888

// Note: O(1) space is possible.

var buf = make([][2]int, 1e5)

func minFlips(s string) int {
	backward := buf[:len(s)]

	from0, from1 := 0, 0
	var alt byte = 0 // alternating byte
	for i := len(s) - 1; i >= 0; i-- {
		if s[i]-'0' == alt {
			from1++
		} else {
			from0++
		}
		alt = alt ^ 1
		backward[i] = [2]int{from0, from1}
	}

	minCost := min(backward[0][0], backward[0][1])
	from0, from1 = 0, 0
	for i := range len(s) - 1 {
		if s[i]-'0' == byte(i%2) {
			from1++
		} else {
			from0++
		}
		minCost = min(
			minCost,
			from0+backward[i+1][1],
			from1+backward[i+1][0],
		)
	}
	return minCost
}

var _ = minFlips