I was thinking for some days about this problem if i can solve in O(n). I still think there must be better than O(n²) algorithm, couldn’t come up with one. Then i decided to start solve in O(n²).

I used expand around concept to find all palindrome strings centered at given point. This would take O(n²) time. when expanding, find update both sides' optimal palindrome partition cut. which will give us optimal solution for the whole string.

I quickly checked other algorithms, they look ridiculously complex and most of them were not original answers and explanation lacked why they have to be the way they are.

`public int minCut(String s) {`

int n = s.length();

char[] t = s.**to**CharArray();

int[] dp = **new** int[n+1];

Arrays.fill(dp, Integer.MAX_VALUE);

dp[0] = -1;

int i = 0;

**while**(i < n) {

expandAround(t, i, i, dp);

expandAround(t, i, i+1, dp);

i++;

}

return dp[n];

}

public void expandAround(char[] t, int i , int j, int[] dp) {

**while**(i >= 0 && j < t.length && t[i] == t[j]) {

dp[j+1] = Math.min(dp[j+1], dp[i]+1);

i--;j++;

}

}