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 <= 105s consists of lowercase English letters.
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
hlen = [0] * n
center = right = 0
for i in range(n):
if i < right:
hlen[i] = min(right - i, hlen[2 * center - i])
while (
0 <= i - 1 - hlen[i]
and i + 1 + hlen[i] < len(s)
and s[i - 1 - hlen[i]] == s[i + 1 + hlen[i]]
):
hlen[i] += 1
if right < i + hlen[i]:
center, right = i, i + hlen[i]
prefix = [0] * n
suffix = [0] * n
for i in range(n):
prefix[i + hlen[i]] = max(prefix[i + hlen[i]], 2 * hlen[i] + 1)
suffix[i - hlen[i]] = max(suffix[i - hlen[i]], 2 * hlen[i] + 1)
for i in range(1, n):
prefix[~i] = max(prefix[~i], prefix[~i + 1] - 2)
suffix[i] = max(suffix[i], suffix[i - 1] - 2)
for i in range(1, n):
prefix[i] = max(prefix[i - 1], prefix[i])
suffix[~i] = max(suffix[~i], suffix[~i + 1])
return max(prefix[i - 1] * suffix[i] for i in range(1, n))(code-box)
class Solution {
public long maxProduct(String s) {
int n = s.length();
if (n == 2) return 1;
int[] len = manachers(s);
long[] left = new long[n];
int max = 1;
left[0] = max;
for (int i = 1; i <= n - 1; i++) {
if (len[(i - max - 1 + i) / 2] > max) max += 2;
left[i] = max;
}
max = 1;
long[] right = new long[n];
right[n - 1] = max;
for (int i = n - 2; i >= 0; i--) {
if (len[(i + max + 1 + i) / 2] > max) max += 2;
right[i] = max;
}
long res = 1;
for (int i = 1; i < n; i++) {
res = Math.max(res, left[i - 1] * right[i]);
}
return res;
}
private int[] manachers(String s) {
int len = s.length();
int[] P = new int[len];
int c = 0;
int r = 0;
for (int i = 0; i < len; i++) {
int mirror = (2 * c) - i;
if (i < r) {
P[i] = Math.min(r - i, P[mirror]);
}
int a = i + (1 + P[i]);
int b = i - (1 + P[i]);
while (a < len && b >= 0 && s.charAt(a) == s.charAt(b)) {
P[i]++;
a++;
b--;
}
if (i + P[i] > r) {
c = i;
r = i + P[i];
}
}
for (int i = 0; i < len; i++) {
P[i] = 1 + 2 * P[i];
}
return P;
}
}(code-box)
class Solution {
public:
long long maxProduct(string s) {
long long res = 0, l = 0, n = s.size();
vector<int> m(n), r(n);
for (int i = 0, l = 0, r = -1; i < n; ++i) {
int k = (i > r) ? 1 : min(m[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k])
k++;
m[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
queue<array<int, 2>> q, q1;
for (int i = n - 1; i >= 0; --i) {
while (!q.empty() && q.front()[0] - q.front()[1] > i - 1)
q.pop();
r[i] = 1 + (q.empty() ? 0 : (q.front()[0] - i) * 2);
q.push({i, m[i]});
}
for (int i = 0; i < n - 1; i++) {
while (!q1.empty() && q1.front()[0] + q1.front()[1] < i + 1)
q1.pop();
l = max(l, 1ll + (q1.empty() ? 0 : (i - q1.front()[0]) * 2));
res = max(res, l * r[i + 1]);
q1.push({i, m[i]});
}
return res;
}
};(code-box)
func maxProduct(s string) int64 {
n := len(s)
hlen := make([]int, n)
center, right := 0, 0
for i := 0; i < n; i++ {
if i < right {
mirror := 2*center - i
if mirror >= 0 && mirror < n {
hlen[i] = min(right-i, hlen[mirror])
}
}
for i-1-hlen[i] >= 0 && i+1+hlen[i] < n && s[i-1-hlen[i]] == s[i+1+hlen[i]] {
hlen[i]++
}
if i+hlen[i] > right {
center = i
right = i + hlen[i]
}
}
prefix := make([]int, n)
suffix := make([]int, n)
for i := 0; i < n; i++ {
r := i + hlen[i]
if r < n {
prefix[r] = max(prefix[r], 2*hlen[i]+1)
}
l := i - hlen[i]
if l >= 0 {
suffix[l] = max(suffix[l], 2*hlen[i]+1)
}
}
for i := 1; i < n; i++ {
if n-i-1 >= 0 {
prefix[n-i-1] = max(prefix[n-i-1], prefix[n-i]-2)
}
suffix[i] = max(suffix[i], suffix[i-1]-2)
}
for i := 1; i < n; i++ {
prefix[i] = max(prefix[i-1], prefix[i])
suffix[n-i-1] = max(suffix[n-i], suffix[n-i-1])
}
var res int64
for i := 1; i < n; i++ {
prod := int64(prefix[i-1]) * int64(suffix[i])
if prod > res {
res = prod
}
}
return res
}(code-box)
