import java.util.*;

class Solution {
    private char[] chs;

    public int minCut(String s) {
        chs = s.toCharArray();
        int len = chs.length;
        int[] dp = new int[len + 1];
        for (int i = 0; i <= len; i++)
            dp[i] = i - 1;
        // dp[i] = dp[k] + 1, if s.substring(k, i + 1) is palindrome
        for (int i = 0; i < len; i++) {
            for (int l = i, r = i; 0 <= l && r < len && chs[l] == chs[r]; l--, r++)
                dp[r + 1] = Math.min(dp[r + 1], dp[l] + 1);
            for (int l = i, r = i + 1; 0 <= l && r < len && chs[l] == chs[r]; l--, r++)
                dp[r + 1] = Math.min(dp[r + 1], dp[l] + 1);
        }
        return dp[chs.length];
    }
}