Formatted question description: https://leetcode.ca/all/1960.html

# 1960. Maximum Product of the Length of Two Palindromic Substrings

## Level

Hard

## Description

You are given a **0-indexed** string `s`

and are tasked with finding two **non-intersecting palindromic** substrings of **odd** length such that the product of their lengths is maximized.

More formally, you want to choose four integers `i`

, `j`

, `k`

, `l`

such that `0 <= i <= j < k <= l < s.length`

and both the substrings `s[i...j]`

and `s[k...l]`

are palindromes and have odd lengths. `s[i...j]`

denotes a substring from index `i`

to index `j`

**inclusive**.

Return *the maximum possible product of the lengths of the two non-intersecting palindromic substrings*.

A **palindrome** is a string that is the same forward and backward. A **substring** is a contiguous sequence of characters in a string.

**Example 1:**

**Input:** s = “ababbb”

**Output:** 9

**Explanation:** Substrings “aba” and “bbb” are palindromes with odd length. product = 3 * 3 = 9.

**Example 2:**

**Input:** s = “zaaaxbbby”

**Output:** 9

**Explanation:** Substrings “aaa” and “bbb” are palindromes with odd length. product = 3 * 3 = 9.

**Constraints:**

`2 <= s.length <= 10^5`

`s`

consists of lowercase English letters.

## Solution

Use Manacher’s Algorithm. For each position in `s`

, find the length of the longest palindrome that has the center at the position. Then find two non-overlapping longest palindromes and return their product.

```
class Solution {
public long maxProduct(String s) {
int length = s.length();
int[] span = new int[length];
for (int i = 0, l = 0, r = -1; i < length; i++) {
span[i] = i <= r ? Math.min(span[l + r - i], r - i + 1) : 1;
while (i - span[i] >= 0 && i + span[i] < length && s.charAt(i - span[i]) == s.charAt(i + span[i]))
span[i]++;
if (i + span[i] - 1 > r) {
l = i - span[i] + 1;
r = i + span[i] - 1;
}
}
int[] pre = new int[length];
int[] suf = new int[length];
for (int i = 0; i < length; i++) {
pre[i + span[i] - 1] = Math.max(pre[i + span[i] - 1], span[i] * 2 - 1);
suf[i - span[i] + 1] = Math.max(suf[i - span[i] + 1], span[i] * 2 - 1);
}
for (int i = 1; i < length; i++)
pre[i] = Math.max(pre[i], pre[i - 1]);
for (int i = length - 2; i >= 0; i--)
pre[i] = Math.max(pre[i], pre[i + 1] - 2);
for (int i = length - 2; i >= 0; i--)
suf[i] = Math.max(suf[i], suf[i + 1]);
for (int i = 1; i < length; i++)
suf[i] = Math.max(suf[i], suf[i - 1] - 2);
long product = 0;
for (int i = 0; i < length - 1; i++)
product = Math.max(product, (long) pre[i] * suf[i + 1]);
return product;
}
}
```