Easy C++, O(n) time and O(1) space without using LPS array


#1
int getMin(int id, string &s)
{
    if(id == s.length()-1) return 0;

    int j = s.length()-1;
    int i = id;
    bool pal = true;
    while(i < j)
    {
        if(s[i] != s[j])
        {
            pal = false;
            break;
        }
        i++,j--;
    }
    if(pal) return 0;

    return (i-id+1) + getMin(i+1, s);

}
int Solution::solve(string A) {

    return getMin(0, A);
}

#2

your solution is recursive. So it will use stack space. In that case space will not be O(1)/