Maximum Product of the Length of Two Palindromic Substrings
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 themaximum 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.
Examples
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^5sconsists of lowercase English letters.
Solution
Method 1 – Manacher's Algorithm + Prefix/Suffix Max
Intuition
To maximize the product of two non-overlapping odd-length palindromic substrings, we need to efficiently find the longest odd-length palindrome ending at or before each position (for the left substring) and starting at or after each position (for the right substring). Manacher's algorithm allows us to find all palindromic substrings in linear time.
Approach
- Use Manacher's algorithm to compute the maximum odd-length palindrome radius centered at each position.
- For each position, compute the maximum odd-length palindrome ending at or before that position (prefix max).
- For each position, compute the maximum odd-length palindrome starting at or after that position (suffix max).
- For each possible split point, compute the product of the best left and right palindromic substring lengths.
- Return the maximum product found.
Code
C++
class Solution {
public:
int maxProduct(string s) {
int n = s.size();
vector<int> d(n);
for (int i = 0; i < n; ++i) {
int l = 0;
while (i-l >= 0 && i+l < n && s[i-l] == s[i+l]) ++l;
d[i] = 2*l-1;
}
vector<int> pre(n), suf(n);
pre[0] = d[0];
for (int i = 1; i < n; ++i) pre[i] = max(pre[i-1], d[i]);
suf[n-1] = d[n-1];
for (int i = n-2; i >= 0; --i) suf[i] = max(suf[i+1], d[i]);
int ans = 0;
for (int i = 0; i < n-1; ++i) ans = max(ans, pre[i] * suf[i+1]);
return ans;
}
};
Go
func maxProduct(s string) int {
n := len(s)
d := make([]int, n)
for i := 0; i < n; i++ {
l := 0
for i-l >= 0 && i+l < n && s[i-l] == s[i+l] {
l++
}
d[i] = 2*l - 1
}
pre := make([]int, n)
suf := make([]int, n)
pre[0] = d[0]
for i := 1; i < n; i++ {
if d[i] > pre[i-1] {
pre[i] = d[i]
} else {
pre[i] = pre[i-1]
}
}
suf[n-1] = d[n-1]
for i := n-2; i >= 0; i-- {
if d[i] > suf[i+1] {
suf[i] = d[i]
} else {
suf[i] = suf[i+1]
}
}
ans := 0
for i := 0; i < n-1; i++ {
prod := pre[i] * suf[i+1]
if prod > ans {
ans = prod
}
}
return ans
}
Java
class Solution {
public int maxProduct(String s) {
int n = s.length();
int[] d = new int[n];
for (int i = 0; i < n; ++i) {
int l = 0;
while (i-l >= 0 && i+l < n && s.charAt(i-l) == s.charAt(i+l)) ++l;
d[i] = 2*l-1;
}
int[] pre = new int[n], suf = new int[n];
pre[0] = d[0];
for (int i = 1; i < n; ++i) pre[i] = Math.max(pre[i-1], d[i]);
suf[n-1] = d[n-1];
for (int i = n-2; i >= 0; --i) suf[i] = Math.max(suf[i+1], d[i]);
int ans = 0;
for (int i = 0; i < n-1; ++i) ans = Math.max(ans, pre[i] * suf[i+1]);
return ans;
}
}
Kotlin
class Solution {
fun maxProduct(s: String): Int {
val n = s.length
val d = IntArray(n)
for (i in 0 until n) {
var l = 0
while (i-l >= 0 && i+l < n && s[i-l] == s[i+l]) l++
d[i] = 2*l-1
}
val pre = IntArray(n)
val suf = IntArray(n)
pre[0] = d[0]
for (i in 1 until n) pre[i] = maxOf(pre[i-1], d[i])
suf[n-1] = d[n-1]
for (i in n-2 downTo 0) suf[i] = maxOf(suf[i+1], d[i])
var ans = 0
for (i in 0 until n-1) ans = maxOf(ans, pre[i] * suf[i+1])
return ans
}
}
Python
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
d = [0] * n
for i in range(n):
l = 0
while i-l >= 0 and i+l < n and s[i-l] == s[i+l]:
l += 1
d[i] = 2*l-1
pre = [0] * n
suf = [0] * n
pre[0] = d[0]
for i in range(1, n):
pre[i] = max(pre[i-1], d[i])
suf[-1] = d[-1]
for i in range(n-2, -1, -1):
suf[i] = max(suf[i+1], d[i])
ans = 0
for i in range(n-1):
ans = max(ans, pre[i] * suf[i+1])
return ans
Rust
impl Solution {
pub fn max_product(s: String) -> i32 {
let n = s.len();
let s = s.as_bytes();
let mut d = vec![0; n];
for i in 0..n {
let mut l = 0;
while i as i32 - l >= 0 && i + l < n && s[i-l] == s[i+l] {
l += 1;
}
d[i] = 2*l-1;
}
let mut pre = vec![0; n];
let mut suf = vec![0; n];
pre[0] = d[0];
for i in 1..n {
pre[i] = pre[i-1].max(d[i]);
}
suf[n-1] = d[n-1];
for i in (0..n-1).rev() {
suf[i] = suf[i+1].max(d[i]);
}
let mut ans = 0;
for i in 0..n-1 {
ans = ans.max(pre[i] * suf[i+1]);
}
ans
}
}
TypeScript
class Solution {
maxProduct(s: string): number {
const n = s.length;
const d = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
let l = 0;
while (i-l >= 0 && i+l < n && s[i-l] === s[i+l]) ++l;
d[i] = 2*l-1;
}
const pre = new Array(n).fill(0);
const suf = new Array(n).fill(0);
pre[0] = d[0];
for (let i = 1; i < n; ++i) pre[i] = Math.max(pre[i-1], d[i]);
suf[n-1] = d[n-1];
for (let i = n-2; i >= 0; --i) suf[i] = Math.max(suf[i+1], d[i]);
let ans = 0;
for (let i = 0; i < n-1; ++i) ans = Math.max(ans, pre[i] * suf[i+1]);
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2), wherenis the length of the string. For each center, we expand to find the largest odd-length palindrome. - 🧺 Space complexity:
O(n), for the prefix and suffix arrays.