class Solution {
public:
    string convert(string s)
    {
        string news = "@";
        int n = s.length();
        for(int i=0;i<n;i++)
        {
            news+="#" + s.substr(i,1);
        }
        news+="#&";
        return news;
    }
    string longestPalindrome(string s) {
        int p[2005];
        for(int i=0;i<2005;i++)p[i]=0;
        string news = convert(s);
        //cout<<news;
        int n = news.length();
        int c=0,r=0;
        for(int i=1;i<n-1;i++)
        {
            int mirror = 2*c-i;
            if(r > i) p[i] = min(p[mirror],r-i);

            while(news[i + 1 + p[i]] == news[i -1 -p[i]])p[i]++;

            if(i+p[i]>r)r =i+p[i],c=i;
        }
        int id=0,mx=0;
        for(int i=1;i<n-1;i++)
        {
            if(mx<p[i])mx = p[i],id=i;
        }

        string ans = s.substr((id - mx -1)/2,mx);
        return ans;

    }
};