<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 Ends:
    start: int
    end: int

    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end

class Solution:
    def longestPalindrome(self, s: str) -> str:
        palindrome_dict = {}
        max_length = 1
        longest = ""

        # Init palindrome dict part 1
        for i in range(len(s)):
            ends = Ends(i, i)
            palindrome_dict[ends] = s[i]

            if len(s[i]) > len(longest):
                longest = s[i]

        # Init palindrome dict part 2
        for i in range(len(s)):
            if i + 1 >= len(s):
                continue

            if s[i] == s[i+1]:
                ends = Ends(i, i+1)
                palindrome_dict[ends] = s[i] + s[i+1]

                if len(s[i] + s[i+1]) > len(longest):
                    longest = s[i] + s[i+1]
        
        while True:
            new_palindrome_dict = {}

            for ends in palindrome_dict.keys():
                new_start = ends.start - 1
                new_end = ends.end + 1

                if new_start < 0 or new_end >= len(s):
                    continue

                if s[new_start] == s[new_end]:
                    new_ends = Ends(new_start, new_end)
                    new_palindrome_dict[new_ends] = s[new_start: new_end+1]

                    if len(s[new_start: new_end+1]) > len(longest):
                        longest = s[new_start: new_end+1]

            if new_palindrome_dict:
                palindrome_dict = new_palindrome_dict
            else:
                break

        return longest
19400