# Share an O(n) solution

• ``````class Solution{
public:
string longestPalindrome(string s){
int size=s.size(),i;
char *t=new char[2*size+2],*q=t;
int *p=new int[2*size+1],mx=0,id=0,MAX=0,center=0;
for(*q='#',i=0;i<size;++i,*++q='#')*++q=s[i];

for(*++q=0,p[0]=i=1;t[i];i++) {
p[i]=mx>i?min(p[2*id-i],mx-i):1;
while(i+p[i]<=2*size+1 && t[i+p[i]]==t[i-p[i]])p[i]++;
if(i+p[i]>mx)mx=i+p[i],id=i;
if(p[i]>MAX)MAX=p[i],center=i;
}
delete(p),delete(t);
return s.substr((center-MAX+1)/2,MAX-1);
}
};
``````

Implement of the Manacher's algorithm, O(n) complexity, just 12ms!

• why do you think it is O(n). Obviously, you have two loops.

• This problem indeed can be solved in O(n). But a minor suggestion for you, the code could be well organized for others to read.

• How ? the best solution for this question is DP, which is O(n^2) in this case.

• This post is deleted!

• I think you should use delete[] p rather than delete(p). Mix up delete[] and delete may cause undefined behavior.

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