# My 0ms C solution

• The main idea is Manacher's Algorithm. This algorithm calculate LPS of each position in linear time. For string s, it makes a new helper string t and an array of palindromic substring length:

s = abbac

T = [ # a # b # b # a # c # ]

P = [ 0 1 0 1 4 1 0 1 0 1 0 ]

int steps[s.length+1] -- how many steps from s[0] to position i. Since every single char is a palindrome string, I init each step[i] with i.

While Manacher's algorithm finds a new palindromic center and right, update each index between center and right, set it to min(step[mirrorIndex(i, center)]+1, step[i]).

``````int minCut(char* s) {
int slen = strlen(s), tlen = slen*2+1, i;
if (slen <= 1)
return 0;

char *t = (char*)malloc(tlen); // helper string t
int *p = (int*)malloc(tlen*sizeof(int)), *steps = (int*)malloc((slen+1)*sizeof(int));

t[0] = '#';
for (i = 0; i < slen; i++) {
t[i*2+1] = s[i];
t[i*2+2] = '#';
steps[i] = i;
}
steps[slen] = slen;

int center = 1, right = 2;
p[0] = 0;
p[1] = 1;

for (i = 2; i < tlen; i++) {
int mirror = center*2 - i;
if (right > i && p[mirror] < right-i) {
p[i] = p[mirror];
continue;
}

int limit = min(i, tlen-i-1), n, j;
for (n = right <= i ? 1 : right+1-i; n <= limit; n++) {
if (t[i+n] != t[i-n])
break;
}

p[center = i] = --n;
right = i + n;

for (j = (i-n)/2; n >= 1; j++, n -= 2) { // update steps
steps[j+n] = min(steps[j+n], steps[j]+1);
}
}

int r = steps[slen]-1;
free(t);
free(p);
free(steps);
return r;
}
``````

The complexity of Manacher's algorithm is O(n). But, since every time the center and right are changing, the updating of steps costs (newRight - newCenter) time, while Manacher's only spends (newRight - oldRight), a little bit more (right-i) makes this algorithm O(n^2).

btw, the JS version was 145ms, while the Java used 300ms...

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