<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 len(s) == 1:
            return s
        elif len(s) == 2:
            if s[0] == s[1]:
                return s
            else:
                return s[0]
            
        best = s[0]
        bestLength = 1
        
        # Checks for even length palidromes
        for i in range(1, len(s) // 2 + 1):
            leftHalf = s[:i]
            temp = s[i:2*i]
            rightHalf = temp[::-1]
            if leftHalf == rightHalf and (len(leftHalf) * 2) > bestLength:
                best = s[:2*i]
                bestLength = len(leftHalf) * 2
        
        
        # Checks for odd length palindromes        
        for i in range(1, len(s) // 2 + 1):
            leftHalf = s[:i]
            temp = s[i+1:2*i+1]
            rightHalf = temp[::-1]
            if leftHalf == rightHalf and (len(leftHalf) * 2 + 1) > bestLength:
                best = s[:2*i + 1]
                bestLength = len(leftHalf) * 2 + 1 
            
        # Recursive call
        withoutFirstChar = self.longestPalindrome(s[1:])
        
        # Returns max between including and excluding first character
        if bestLength >= len(withoutFirstChar):
            return best
        else:
            return withoutFirstChar
18700