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