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

import math

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # candidates = [[int(x/2)] if (x/2).is_integer() else [int(x/2-0.5), int(x/2+0.5)] for x in range(0, 5*2 + 1)]
        candidates = []
        answer = ""
        for i in range(len(s)):
            candidates.append([i, i])
            if i+1 < len(s) and s[i] == s[i+1]:
                candidates.append([i, i+1])
                answer = s[i: i+2]
        if len(answer) < 2:
            answer = s[0]
        # print(f"candidates={candidates}")
        while len(candidates) > 0:
            left_index, right_index = candidates.pop(0)
            if (right_index + 1) >= len(s) or (left_index - 1) < 0:
                continue
            if s[left_index-1] == s[right_index+1]:
                candidates.append([left_index-1, right_index+1])
                if len(s[left_index -1: right_index + 2]) > len(answer):
                    answer = s[left_index -1: right_index + 2]
        # print(f"answer={answer}")
        return answer



    # memo = {}

    # def longestPalindrome(self, s: str) -> str:
    #     if s in self.memo:
    #         print(f"found {s} in")
    #         return self.memo[s]
    #     if self.isPalindrome(s):
    #         self.memo[s] = s
    #         return s
    #     right = self.longestPalindrome(s[1:])
    #     self.memo[s[1:]] = right
    #     left = self.longestPalindrome(s[:-1])
    #     self.memo[s[:-1]] = left
    #     if len(left) > len(right):
    #         return left
    #     return right

    # def isPalindrome(self, s):
    #     for i in range(math.ceil(len(s)/2)):
    #         if s[i] != s[-1-i]:
    #             return False
    #     return True
17000