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

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

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;
}
}