package main

func minCutSlow(s string) int { // Too slow :(
	n := len(s)
	if n <= 1 {
		return 0
	}
	cutCnt := make([]int, n+1)
	cutCnt[0] = 1
	for i := 0; i < n; i++ {
		if cutCnt[i] != 0 {
			for j := i + 1; j <= n; j++ {
				if isPalindrome(s, i, j) {
					if cutCnt[j] == 0 {
						cutCnt[j] = cutCnt[i] + 1
					} else if cutCnt[i] < cutCnt[j] {
						cutCnt[j] = cutCnt[i] + 1
					}
				}
			}
		}
	}
	return cutCnt[n] - 2
}

func isPalindrome(s string, beg, end int) bool { // End is not included
	for ; beg < end; beg, end = beg+1, end-1 {
		if s[beg] != s[end-1] {
			return false
		}
	}
	return true
}

func minCut(s string) int {
	n := len(s)
	if n <= 1 {
		return 0
	}
	dp := make([]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = i - 1
	}
	for i := 0; i < n; i++ {
		// For example, 'aba' and i = 1
		for j := 0; 0 <= i-j && i+j < n && s[i-j] == s[i+j]; j++ {
			if dp[i-j] < dp[i+j+1] {
				dp[i+j+1] = dp[i-j] + 1
			}
		}
		// For example, 'abba' and i = 1
		for j := 1; 0 <= i-j+1 && i+j < n && s[i-j+1] == s[i+j]; j++ {
			if dp[i-j+1] < dp[i+j+1] {
				dp[i+j+1] = dp[i-j+1] + 1
			}
		}
	}
	return dp[n]
}

// func main() {
// 	println(minCut("abb"))
// 	println(minCut("aab"))
// 	println(minCut("abbbbbb"))
// }