<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:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return s
        if len(s)<=2:
            if s==s[::-1]:
                return s
            else:
                return s[0]
        if s==s[::-1]:
            return s
        dp=[]
        cur = []
        for i in range(len(s)):
            cur.append(i)
        dp.append(cur)
        cur = []
        for i in range(len(s)-1):
            a = s[i:i+2]
            if a==a[::-1]:
                cur.append(i)
        dp.append(cur)
        for i in range(3,len(s)+1):
            print(i)
            cur = []
            for j in dp[-2]:
                if j>0 and j+i<len(s)+2:
                    # if i==3:
                        # print(j-1,j+i-2)
                    if s[j-1]==s[j+i-2]:
                        cur.append(j-1)
            # if not cur and not dp[-1]:
            #     for j in dp[-1]:
            #         return s[j:i+j-1]
            #     for j in dp[-1]:
            #         return s[j:i+j-2]
            dp.append(cur)
        ind = -1
        for i in range(len(s)):
            if dp[i]:
                ind = i
        return s[dp[ind][0]:dp[ind][0]+ind+1]
23600