package main

import (
	"fmt"
	"math"
)

func partition(s string) int {
	n := len(s)
	if n == 0 || n == 1 {
		return 0
	}
	mem := make(map[int]map[int]int)
	for i := 0 ; i < n ; i ++ {
		mem[i] = make(map[int]int)
	}
	res := make([][]string,0,0)
	var backTrace func (l ,r int , str string, tmp []string)
	backTrace = func(l, r int, str string ,tmp []string) {
		if l == r {
			res = append(res, tmp)
		}
		for i := l + 1 ; i <= r ; i ++ {
			sub := str[l:i]
			if mem[l][i] == 1 ||  IsPalindrome(sub){
				mem[l][i] = 1
				tmp = append(tmp, sub)
				backTrace(i ,r ,str , append([]string{} , tmp...))
				tmp = tmp[:len(tmp)-1]
				continue
			}
		}
	}
	backTrace(0,n,s,[]string{})
	times := math.MaxInt32
	for _ , a  := range res {
		times = min(times , len(a))
	}
	return times - 1
}

func IsPalindrome (s string) bool {
	n := len(s)
	for i := 0 ; i < n / 2 ; i++ {
		if s[i] != s[n-i-1] {
			return false
		}
	}
	return true
}

func main() {
	fmt.Println(partition("aab"))
}