<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>

/*
"abcba"
"aaaaa"
"cbbd"
"aacabdkacaa"
*/

class Solution {
public:
    string longestPalindrome(string s) {
        int **v=(int **)malloc(s.size()*sizeof(int *));
        int max=0,ii=0,jj=0;

        if(s.length()==1)
            return s;
        if(s.length()==2)
        {
            if(s[0]==s[1])
            {
                return s;        
            }
            else
            {
                string t(s,0,1);
                return t;
            }            
        }
        for(int i=0;i<s.size();i++)
        {
            v[i]=(int *)calloc(s.size(),sizeof(int));            
        }            
         
        for(int x=0;x<s.size();x++)
        {
            int y=x+1;
            v[x][x]=1;            
            while(y<s.size() && s[x]==s[y])            
                y++;
                        
                v[x][y-1]=1;
                if(y-1-x > max)
                {
                    ii=x;
                    jj=y-1;
                    max=jj-ii;
                   // printf("0v[%d][%d]=1 max: %d\n",x,y-1,max);          
                }
            x=y-1;
        }
 
       // char dp[s.size()-1][s.size()-1]={-1,};
        for(int i=0;i<s.size()-1;i++)
        {
            for(int j=i+1;j<s.size();j++)
            {  
               v[i][j]=((s[i]==s[j])&&(v[i+1][j-1]));                              
                if(v[i][j])
                {   
                    int x=i,y=j;
                    //printf("v[%d][%d]=%d max %d\n",x,y,v[x][y],max);
                    while(y<s.size() && x>=0 && (s[x]==s[y]))
                    {
                      // printf("v[%d][%d]=%d max %d\n",x,y,v[x][y],max);
                        v[x][y]=1;
                        if(y-x > max)
                        {
                            max=y-x;
                            jj=y;ii=x;
                        }
                        y++; x--;
                    }                                        
                }
            }
        }
        //printf("ii %d jj %d\n",ii,jj);
        return s.substr(ii,jj-ii+1);
    }
};
283104