# Java 10ms (99.25%) solution

• We do 2 things to solve the problem,

1. Use Manacher's alogorithm to find all palindromes in the string.

2. Use DP to find the min cut.

public class Solution {
public int minCut(String s) {
int len;

``````     if (s == null || (len = s.length()) == 0) {
return 0;
}

int[] cntP = cntPalin(seq);
int[] dp = new int[len];
int res = len;
int i2;
int j2;
int c;
int tmp;

dp[0] = 1;

for (int i = 1; i < len; i++) {
for (int j = 0; j <= i; j++) {
i2 = i * 2 + 1;
j2 = j * 2 + 1;
c = (i2 + j2) / 2;

// is palin from j to i
if (i2 - c < cntP[c]) {
if (j == 0) {
tmp = 0;
}
else {
tmp = dp[j - 1];
}

if (dp[i] == 0) {
dp[i] = tmp + 1;
}
else {
dp[i]= Math.min(dp[i], tmp + 1);
}
}
}
}

return dp[len - 1] - 1;
}

private int[] cntPalin(char[] seq) {
int len = seq.length;
int[] cnt = new int[len];

cnt[0] = 0;
cnt[1] = 1;

int c = 1;
int r = 1;
int lk;
int i;
int j;

for (int k = 2; k < len; k++) {
i = -1;
j = -1;

if (k > r) {
cnt[k] = 0;
i = k - 1;
j = k + 1;
}
else {
lk = 2 * c - k;

if (r - k > cnt[lk]) {
cnt[k] = cnt[lk];
}
else {
cnt[k] = r - k;
j = r + 1;
i = 2 * k - j;
}
}

while (i >= 0 && j < len && seq[i] == seq[j]) {
cnt[k]++;
i--;
j++;
}

if (k + cnt[k] > r) {
c = k;
r = k + cnt[k];
}

}

return cnt;
}

int len = s.length();
char[] barred = new char[2 * len + 1];
int i = 0;

for (char c : s.toCharArray()) {
barred[i++] = '|';
barred[i++] = c;
}

barred[i] = '|';

return barred;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.