<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 get_all_sub_strings(self, s: str, longest_pal_sub_string: str, checked_sub_string_set: set) -> str:
        if len(s) == 1:
            return s if s == s[::-1] and len(s) > len(longest_pal_sub_string) else longest_pal_sub_string

        running_sub_string = ''
        for ch in s:
            running_sub_string += ch
            if running_sub_string == running_sub_string[::-1] and len(running_sub_string) > len(longest_pal_sub_string):
                longest_pal_sub_string = running_sub_string

        new_sub_string = s[1:]
        if new_sub_string in checked_sub_string_set or new_sub_string[::-1] in checked_sub_string_set:
            return longest_pal_sub_string
        else:
            checked_sub_string_set.add(new_sub_string)
            return self.get_all_sub_strings(new_sub_string, longest_pal_sub_string, checked_sub_string_set) 

    def longestPalindrome(self, s: str) -> str:
        checked_sub_string_set = set()
        longest_pal_sub_string = ''
        return self.get_all_sub_strings(s, longest_pal_sub_string, checked_sub_string_set)

       
        
17800