Elegant O(N^2) solution with O(1) space using LPS


#1

You may look at the “Minimum Characters required to make a String Palindromic” question to understand the solution

    int findLPS(string k){
        vector <int> lps;
        lps.push_back(0);
        int len=0;
        int i=1;
        while(i<k.size()){
            if(k[i]==k[len]){
                len++;
                lps.push_back(len);
                i++;
            }
            else{
                if(len!=0)
                    len = lps[len-1];
                else{
                    lps.push_back(0);
                    i=0;
                }
            }
        }
        return lps[A.size()-1];
    }
    string Solution::longestPalindrome(string A) {
        int mx=0;
        string ms="";
        for(int i=0;i<A.size();i++){
            string t = A.substr(i);
            string b = t;
            reverse(b.begin(),b.end());
            string k = t+'.'+b; // suffix of original string + . + reverse of the suffix
            
            int a = findLPS(k);
            if(a>mx)
            {
                mx=a;
                ms=k.substr(0,mx);
            }
        }
        return ms;
    }

#2

it is using o(n) space