Simple c++ solution with with time complexity O(n^2) and space Complexity O(n)


#1

string Solution::longestPalindrome(string A) {
int n=A.length(),ans=0,start=0,end=0;string s="";
for(int i=0;i<2n+1;i++)
{
if(i%2==0)
s+=’ ';
else
s+=(A[i/2]);
}
// cout<<s<<"\n";
for(int i=1;i<2
(n);i++)
{
int len=0;
int j=i-1,k=i+1;
while(j>=0&&(k<=(2*n)))
{
if(s[j]==s[k])
len++;
else
break;
j–;
k++;
}
if(ans<len)
{
// cout<<j<<" “<<k<<” “<<i<<”\n";
ans=len;
start=j+1;
end=k-1;
}
}
string s1="";
for(int j=start;j<=end;j++)
{
if(s[j]!=’ ')
s1+=s[j];
}
return s1;
}