<p>You are given a <strong>0-indexed</strong> string <code>s</code> and are tasked with finding two <strong>non-intersecting palindromic </strong>substrings of <strong>odd</strong> length such that the product of their lengths is maximized.</p>

<p>More formally, you want to choose four integers <code>i</code>, <code>j</code>, <code>k</code>, <code>l</code> such that <code>0 &lt;= i &lt;= j &lt; k &lt;= l &lt; s.length</code> and both the substrings <code>s[i...j]</code> and <code>s[k...l]</code> are palindromes and have odd lengths. <code>s[i...j]</code> denotes a substring from index <code>i</code> to index <code>j</code> <strong>inclusive</strong>.</p>

<p>Return <em>the <strong>maximum</strong> possible product of the lengths of the two non-intersecting palindromic substrings.</em></p>

<p>A <strong>palindrome</strong> is a string that is the same forward and backward. A <strong>substring</strong> is a contiguous sequence of characters in a string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ababbb&quot;
<strong>Output:</strong> 9
<strong>Explanation:</strong> Substrings &quot;aba&quot; and &quot;bbb&quot; are palindromes with odd length. product = 3 * 3 = 9.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;zaaaxbbby&quot;
<strong>Output:</strong> 9
<strong>Explanation:</strong> Substrings &quot;aaa&quot; and &quot;bbb&quot; are palindromes with odd length. product = 3 * 3 = 9.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def maxProduct(self, s: str) -> int:
        # find two palindromes of odd length, disjoint
        # return max product of lengths of two

        # there's an O(N) way to find longest palindromes in the input string
        # if we scan that left to right we get longest among indices <= i
        # and if we scan right to left we'd have longest among indices >= i

        ### so how can we get the longest palindrome present in range lo..hi?

        # Manacher's is the obvious choice

        # But I don't know Manacher's

        # So is there a guess-and-check solution?

        # suppose the longest palindrome is length 2*k+1
        # then we can form rolling hashes of the form    c0*A**(k-1) + c1*A**(k-2) + ... + c_{k-1} // forward
        # record the (fwd, i) pairs we saw
        # a palindrome is of the form P middle rev(P)
        # so we need to quickly find P using rev(P)
        # the rolling hash of the reversed string is the one using the "opposite" convention where the last char has max power
        # we can scan the other direction


        # so for each 0..i, O(N) chars, we can find the longest palindrome in O(N log(N))
        # but then we use O(N**2 log(N)), yikes

        # better: we can ask what the longest palindrome centered on i is
        #   suppose we can look up if i-k to i+k is a palindrome

        #  prior_k i next_k
        #   fwd_rh    rev_rh

        # where fwd_rh has biggest pow first, rev_rh has biggest pow last

        # can get fwd_rh of length k by
        #     getting fwd_rh ending i-1
        #     getting fwd_rh ending i-1-k (or 0 if oob)
        #        > scaling this up by k and subtracting it off

        # so in O(N log(N)) we can get biggest palindrome centered on each character

        # then we can transform to biggest palindrome ending at <= i?

        # from peeking at solutions again: yes, with stack stuff?
        # 
        # for 0..j we'll have a bunch of (i, k(i)) pairs for i <= j
        #
        # if i+k(i) <= j then the full 1+2*k(i) is known and exists among indices <= j, we know it's contribution
        # forever so we can add it to the max and continue
        #
        # otherwise leave it in a deque until j is >= right edge

        # 0. preliminaries, rolling hashes are prevHash*A + currOffset
        n = len(s)
        M = 2**31 - 1 # big prime, modulus
        A = 26 # alphabet size, rolling hash factor
        oa = ord('a')

        # cache powers of A mod M for speed
        pow_mod = [1]*n # A**i mod M
        for i in range(1, n): pow_mod[i] = (pow_mod[i-1] * A) % M

        # 1. get rolling hashes from the left and to the right
        #       left hashes and right hashes are mirrored so we can easily find palindromes;
        #       for a central character `i` we need to see some hash(P), i, hash(rev(P))
        left_hashes = [0]*n
        left_hashes[0] = ord(s[0])-oa
        for i in range(1, n):
            left_hashes[i] += left_hashes[i-1]*A + ord(s[i]) - oa
            left_hashes[i] %= M

        right_hashes = [0]*n
        right_hashes[-1] = ord(s[-1]) - oa
        for i in range(n-2, -1, -1):
            right_hashes[i] += right_hashes[i+1]*A + ord(s[i]) - oa
            right_hashes[i] %= M

        # 2. find k such that i-k .. i+k is a palindrome for each i
        def longestPalindromeK(i: int) -> int:
            """Returns the max k such that i-k..i+k is a palindrome"""
            # strategy: binary search on k | i-k .. i+k is a palindrome

            # optimization: in most cases we can return quickly
            if i == 0 or i == n-1 or s[i-1] != s[i+1]: return 0

            lo = 0
            hi = min(i, n-i-1)
            while lo < hi:
                k = (lo+hi+1)//2
                prior = left_hashes[i-1] - (left_hashes[i-1-k] if i-1-k >= 0 else 0)*pow_mod[k]
                later = right_hashes[i+1] - (right_hashes[i+1+k] if i+1+k < n else 0)*pow_mod[k]
                if (prior - later) % M == 0:
                    lo = k
                else:
                    hi = k-1

            return hi

        ks = list(longestPalindromeK(i) for i in range(n))

        # 3. find longest to the left and longest to the right for each index
        longest_left = [0]*n
        max_k = 0
        candidates = deque() # (j, k(j)) pairs for j <= i
        for i in range(n):
            candidates.append((i, ks[i]))
            while candidates and candidates[0][0] + candidates[0][1] < i:
                # earliest (j, k(j)) ends before i, no longer a contender now
                # (we already included it's max k contribution in the prior iteration)
                candidates.popleft()

            # we know first element has j,k(j) | j + k(j) <= i, so we know that j-(i-j) to j+(j-i)==i is a palindrome
            # and thus that has a potential new best k of i-j
            max_k = max(max_k, i-candidates[0][0])

            longest_left[i] = max_k

        # TODO: remove code duplication, wrap this in a method where the direction is a variable
        longest_right = [0]*n
        max_k = 0
        candidates = deque()
        for i in range(n-1, -1, -1):
            candidates.append((i, ks[i]))
            while candidates and candidates[0][0] - candidates[0][1] > i:
                candidates.popleft()

            max_k = max(max_k, candidates[0][0] - i)
            longest_right[i] = max_k

        # 4. final O(N) scan to get the maximum product
        ans = 0
        for i in range(n-1):
            left_len = longest_left[i]*2 + 1
            right_len = longest_right[i+1]*2 + 1
            ans = max(ans, left_len * right_len)

        return ans
2246