<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 hash_of_str(self, s, digits):
        char_values = {c: i + 1 for i, c in enumerate(digits)}
        P = len(digits) + 1
        h = 0
        p = 1
        hashes = [0]
        ps = [1]

        for i in range(len(s)):
            h = h * P + char_values[s[i]]
            hashes.append(h)
            p = p * P
            ps.append(p)
        return hashes, ps

    def hash_of_substr(self, hashes, ps, substr_left, substr_right):
        return hashes[substr_right] - hashes[substr_left] * ps[substr_right - substr_left]

    def find(self, l, center, ss_hashes, ssr_hashes, left, right, ssps, ssrps):
        if left == right:
            return left

        if left == right - 1:
            ss_right_hash = self.hash_of_substr(ss_hashes, ssps, center, right + 1)
            ssr_right_hash = self.hash_of_substr(ssr_hashes, ssrps, l - center - 1, l - 2 * center + right)
            if ss_right_hash == ssr_right_hash:
                return right
            else:
                return left

        middle = (left + right) // 2
        ss_middle_hash = self.hash_of_substr(ss_hashes, ssps, center, middle + 1)
        ssr_middle_hash = self.hash_of_substr(ssr_hashes, ssrps, l - center - 1, l - 2 * center + middle)

        if ss_middle_hash == ssr_middle_hash:
            left = middle
        else:
            right = middle
        return self.find(l, center, ss_hashes, ssr_hashes, left, right, ssps, ssrps)

    def longestPalindrome(self, s: str) -> str:
        ss = []
        for c in s:
            ss.append('$')
            ss.append(c)
        ss.append('$')
        ssr = reversed(ss)
        l = len(ss)
        ss = ''.join(ss)
        ssr = ''.join(ssr)
        digits = ''.join(set(s).union({'$'}))
        ss_hashes, ssps = self.hash_of_str(ss, digits)
        ssr_hashes, ssrps = self.hash_of_str(ssr, digits)
        max_len = 0
        longest_pal = [0, 1]
        half = l // 2
        iters = [half]
        for i in range(half):
            iters.append(half - i)
            iters.append(half + i)
        for i in iters:
            if 2 * i + 1 <= max_len or 2 * (l - 1 - i) + 1 <= max_len:
                continue
            center = i
            left = i
            right = min(i * 2, l - 1)
            end = self.find(l, center, ss_hashes, ssr_hashes, left, right, ssps, ssrps)
            pal_len = 2 * (end - center) + 1
            if pal_len > max_len:
                max_len = pal_len
                longest_pal = [2 * center - end, end + 1]
            # print(ss[2 * center - end: end + 1])
        pal_ss = ss[longest_pal[0]: longest_pal[1]]
        pal = ''.join([pal_ss[2 * i + 1] for i in range(max_len // 2)])
        return pal


if __name__ == "__main__":
    s = Solution()
    ss = 'abac'
    print(s.longestPalindrome(ss))
23300