<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:
        current_palindromes = []
        for ind in range(len(s)):
            current_palindromes.append((ind, ind))
            if ind < len(s) - 1 and s[ind] == s[ind + 1]:
                current_palindromes.append((ind, ind+1))
        print(current_palindromes)
            
        longest = max(current_palindromes, key=lambda x: x[1] - x[0])
        progress = True
        while progress:
            # print('here')
            progress = False
            next_palindromes = []
            for inds in current_palindromes:
                ind = inds[0]
                end_ind = inds[1]
                if ind - 1 >= 0 and end_ind + 1 < len(s) and s[ind - 1] == s[end_ind + 1]:
                    progress = True
                    next_palindromes.append((ind - 1, end_ind + 1))
            # print(next_palindromes)
            if progress:
                new_longest = max(next_palindromes, key=lambda x: x[1] - x[0])
                # print(new_longest)
                if new_longest[1] - new_longest[0] > longest[1] - longest[0]:
                    longest = new_longest
            current_palindromes = next_palindromes

        return s[longest[0]:longest[1]+1]

        
17400