Welcome to Subscribe On Youtube
1960. Maximum Product of the Length of Two Palindromic Substrings
Description
You are given a 0indexed string s
and are tasked with finding two nonintersecting 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 nonintersecting 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 nonoverlapping 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; } }