<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:
        tail = len(s) - 1
        out_str = ""
        out_str_len = 0
        #TODO: speedup by finding instances of c_i's and jumping there
        for c_i in range(len(s)):
            c_is = []
            c_i_pos = 0
            curr_prob_space = len(s[c_i:])
            
            if out_str_len >= curr_prob_space:
                break

            curr_len = 0
            i, j, j_start = c_i, tail, tail
            while i < j:
                if s[c_i] == s[j]:
                    c_is.append(j)

                if s[i] == s[j]:
                    i += 1
                    j -= 1
                    curr_len += 2
                else:
                    i = c_i
                    curr_len = 0
                    if len(c_is) > 0 and c_i_pos < len(c_is):
                        j_start = min(c_is[c_i_pos], j_start-1)
                        c_i_pos += 1
                    else:
                        j_start -= 1
                    j = j_start

            if len(s[c_i:j_start+1]) % 2 == 1:
                curr_len += 1
            if curr_len > out_str_len:
                out_str_len = curr_len
                out_str = s[c_i:j_start+1]
        return out_str
        



        
21600