Very easy solution O(n) without LPS array


#1

int Solution::solve(string A) {
int i=0;
int j=A.size()-1;
while(i<=j)
{
if(A[i]!=A[j] && j==A.size()-1)
i++;

    if(A[i]==A[j])
    {
        i++;
        j--;
    }
    
    if(A[i]!=A[j]&&j!=A.size()-1)
    {
        j=A.size()-1;
    }
    
}
if(j!=A.size()-1)
return i-A.size()+j+1;
return i-1;

}


#2

you should return i, instead of i-1.


#3

No i-1 , as if no character is same from ending then, i will be A.size(), we need to return i-1 because we don’t need to append last character to make it palindrome, it will be middle most character after making palindrome.


#5

your output is wrong for input = “eeefee”, test case is weak and your solution incorrect. I think these improvement will work fine.

int Solution::solve(string A) {
int i=0;
int j=A.size()-1;
int temp=1;
while(i<j)
{
if(A[i]!=A[j] && j==A.size()-1)
{i+=1;}
temp=i+1;
while(i<j&&A[i]==A[j])
{
i++;
j–;
}

if(A[i]!=A[j]&&j!=A.size()-1)
{
    j=A.size()-1;i=temp;
}

}
return temp-1;
}