<p>Given a string <code>s</code>, return <em>the longest</em> <span data-keyword="palindromic-string"><em>palindromic</em></span> <span data-keyword="substring-nonempty"><em>substring</em></span> in <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babad&quot;
<strong>Output:</strong> &quot;bab&quot;
<strong>Explanation:</strong> &quot;aba&quot; is also a valid answer.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbbd&quot;
<strong>Output:</strong> &quot;bb&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consist of only digits and English letters.</li>
</ul>

class Solution {
public:

    void buildlps(string &a , vector<int> &lps){
        int n=a.size();
        int i=1;
        int len=0;
        while(i<n){
            if(a[i]==a[len]){
                lps[i]=len+1;
                i++;
                len++;
            }
            else {
                if(len==0){
                    lps[i]=0;
                    i++;
                }
                else{
                    len=lps[len-1];
                }
            }
        }
    }

    string longestPalindrome(string s) {
        int n1=s.size();
        string ans="";
        string a="@";
        for(int i=(n1-1);i>=0;i--){
            a=s[i]+a+s[i];
            int n2=a.size();
            vector<int> lps(n2,0);
            buildlps(a,lps);
            //ans=max(ans,lps[n2-1]);
            if(lps[n2-1]>ans.size()) ans=a.substr(0,lps[n2-1]);
        }
        return ans;
    }
};
367751