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 <= 105sconsists of lowercase English letters.
Companies:
Codenation
Related Topics:
String, Rolling Hash, Hash Function
// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/discuss/1389958/Manacher-and-Queue
class Solution {
public:
long long maxProduct(string s) {
int N = s.size(), j = 0;
vector<int> r(N, 1);
for (int i = 1; i < N; ++i) {
int cur = j + r[j] > i ? min(r[2 * j - i], j + r[j] - i) : 1;
while (i - cur >= 0 && i + cur < N && s[i - cur] == s[i + cur]) ++cur;
if (i + cur > j + r[j]) j = i;
r[i] = cur;
}
vector<int> right(N, 1); // right[i] is the length of the longest palinedome in [i, n)
queue<array<int, 2>> q, q1; // index, range
for (int i = N - 1; i >= 0; --i) {
while (q.size() && q.front()[0] - q.front()[1] >= i) q.pop(); // if the queue front's range can't cover `i`, pop it.
q.push({i, r[i]});
right[i] = 1 + (q.front()[0] - i) * 2; // now queue front is the rightmost range that can cover `i`. It must be the center of the longest palindrom in `[i, n)`.
}
int left = 0; // left is the length of the longest palindrome in [0, i].
long long ans = 1;
for (int i = 0; i < N - 1; ++i) {
while (q1.size() && q1.front()[0] + q1.front()[1] <= i) q1.pop();
q1.push({i, r[i]});
left = max(left, 1 + (i - q1.front()[0]) * 2);
ans = max(ans, (long long)left * right[i + 1]);
}
return ans;
}
};Or
// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/discuss/1389958/Manacher-and-Queue
class Solution {
vector<int> manacher(string s, int N) {
vector<int> r(N, 1), mx(N, 1);
int j = 0;
for (int i = 1; i < N; ++i) {
int cur = j + r[j] > i ? min(r[2 * j - i], j + r[j] - i) : 1;
while (i - cur >= 0 && i + cur < N && s[i + cur] == s[i - cur]) {
mx[i + cur] = 2 * cur + 1; // now `mx[i]` is the length of the longest palindrome ending at `s[i]`.
++cur;
}
if (i + cur > j + r[j]) j = i;
r[i] = cur;
}
for (int i = 1; i < N; ++i) mx[i] = max(mx[i], mx[i - 1]); // now `mx[i]` is the length of the longest palindrome in `s[0..i]`.
return mx;
}
public:
long long maxProduct(string s) {
long long ans = 1, N = s.size();
auto l2r = manacher(s, N);
auto r2l = manacher(string(rbegin(s), rend(s)), N);
for (int i = 0, j = N - 2; i < N - 1; ++i, --j) {
ans = max(ans, (long long)l2r[i] * r2l[j]);
}
return ans;
}
};