Maximum Product of the Length of Two Palindromic Substrings LeetCode solution in Python

1
class Solution:
2
    def maxProduct(self, s: str) -> int:
3
        n = len(s)
4

5
        # Manacher's algo
6
        hlen = [0] * n  # half-length
7
        center = right = 0
8
        for i in range(n):
9
            if i < right:
10
                hlen[i] = min(right - i, hlen[2 * center - i])
11
            while (
12
                0 <= i - 1 - hlen[i]
13
                and i + 1 + hlen[i] < len(s)
14
                and s[i - 1 - hlen[i]] == s[i + 1 + hlen[i]]
15
            ):
16
                hlen[i] += 1
17
            if right < i + hlen[i]:
18
                center, right = i, i + hlen[i]
19

20
        prefix = [0] * n
21
        suffix = [0] * n
22
        for i in range(n):
23
            prefix[i + hlen[i]] = max(prefix[i + hlen[i]], 2 * hlen[i] + 1)
24
            suffix[i - hlen[i]] = max(suffix[i - hlen[i]], 2 * hlen[i] + 1)
25

26
        for i in range(1, n):
27
            prefix[~i] = max(prefix[~i], prefix[~i + 1] - 2)
28
            suffix[i] = max(suffix[i], suffix[i - 1] - 2)
29

30
        for i in range(1, n):
31
            prefix[i] = max(prefix[i - 1], prefix[i])
32
            suffix[~i] = max(suffix[~i], suffix[~i + 1])
33

34
        return max(prefix[i - 1] * suffix[i] for i in range(1, n))