Maximum Product of the Length of Two Palindromic Substrings solution and explanation
3 more videos on this problem
LeetCode 1960. Maximum Product of the Length of Two Palindromic SubstringsHappy Coding · 30:14 · 1K views
1960. Maximum Product of the Length of Two Palindromic Substrings (Leetcode Hard)Programming Live with Larry · 40:45 · 535 views
【每日一题】LeetCode 1960. Maximum Product of the Length of Two Palindromic Substrings, 8/29/2021Huifeng Guan · 44:37 · 487 views
LeetCode 1960: Maximum Product of the Length of Two Palindromic SubstringsAlitaCode · 28:18 · 9 views
The 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 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.
Approach overview
Problem Overview: Given a string s, choose two non-overlapping palindromic substrings such that the product of their lengths is maximized. The substrings must not share indices, so the problem becomes finding the best palindrome on the left of a split and the best palindrome on the right.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Generate every substring and check whether it is a palindrome by comparing characters from both ends. Store all palindromic intervals, then try every pair and ensure they do not overlap. Compute the product of their lengths and keep the maximum. This approach performs O(n^2) substring checks and each check costs O(n), which makes it impractical for large inputs but useful for understanding the structure of the problem.
Approach 2: Expand Around Center with Prefix/Suffix Best (O(n^2) time, O(n) space)
Use the classic palindrome expansion technique from the string toolbox. For each index, expand outward to detect odd and even length palindromes. Track the maximum palindrome length that ends at or before every position using a left[] array, and similarly track the maximum palindrome length that starts at or after each index using a right[] array. After processing all centers, iterate over every split point i and compute left[i] * right[i+1]. The maximum product across all splits is the answer. The key insight is converting the problem into two independent palindrome searches separated by a boundary.
Approach 3: Manacher's Algorithm / Rolling Hash Optimization (O(n) time, O(n) space)
Manacher’s algorithm computes the longest palindrome radius centered at every position in linear time. With these radii, you can derive the longest palindrome ending at each index and starting at each index, similar to the previous approach but much faster. Another alternative is verifying palindromes using rolling hash and a hash function to compare substrings in constant time. Both techniques reduce repeated character comparisons and allow near-linear processing of candidate palindromes.
Recommended for interviews: The expand-around-center approach is the most practical explanation during interviews. It demonstrates clear understanding of palindrome generation and array precomputation while staying easy to implement. Mentioning Manacher’s algorithm shows deeper algorithm knowledge and signals strong string-processing skills.
Approach 1: Expand Around Center for Palindromes
This approach involves expanding around potential centers of palindromes in the string to find all possible palindromic substrings. By iterating through the string and treating each character and each pair of characters as a potential center of a palindrome, you can identify all odd-length palindromes. This allows determining the longest possible palindrome around each center in a single pass.
def maxProductEvenPalindromes(s):
n = len(s)
max_product = 0
for center in range(n):
length = 0
while center - length >= 0 and center + length < n and s[center - length] == s[center + length]:
current_length = 1 + 2 * length
right_center = center + length + 1
while right_center + length < n and s[right_center - length] == s[right_center + length]:
right_length = 1 + 2 * length
max_product = max(max_product, current_length * right_length)
right_center += 1
length += 1
return max_product
s = "zaaaxbbby"
print(maxProductEvenPalindromes(s))public class Main {
public static int maxProductEvenPalindromes(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxProduct = 0;
for (int gap = 0; gap < n; gap++) {
for (int i = 0, j = gap; j < n; i++, j++) {
if (gap == 0) {
dp[i][j] = true;
} else if (gap == 1) {
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
}
if (dp[i][j] && (j - i + 1) % 2 == 1) {
for (int k = 0; k < i; k++) {
for (int l = k; l < j; l++) {
if (dp[k][l] && (l - k + 1) % 2 == 1) {
maxProduct = Math.max(maxProduct, (j - i + 1) * (l - k + 1));
}
}
}
}
}
}
return maxProduct;
}
public static void main(String[] args) {
String s = "zaaaxbbby";
System.out.println(maxProductEvenPalindromes(s));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int maxProductEvenPalindromes(string s) {
int n = s.size();
int maxProduct = 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int length = 1; length <= n; length += 2) {
for (int i = 0; i + length - 1 < n; ++i) {
int j = i + length - 1;
if (s[i] == s[j] && (length == 1 || dp[i + 1][j - 1])) {
dp[i][j] = true;
for (int k = 0; k < i; ++k) {
for (int l = k; l < j; ++l) {
if (s[k] == s[l] && dp[k][l] && (l - k + 1) % 2) {
maxProduct = max(maxProduct, (j - i + 1) * (l - k + 1));
}
}
}
}
}
}
return maxProduct;
}
int main() {
string s = "zaaaxbbby";
cout << maxProductEvenPalindromes(s) << endl;
return 0;
}function maxProductEvenPalindromes(s) {
let maxProduct = 0;
const n = s.length;
const isPalindrome = (start, end) => {
while (start < end) {
if (s[start] !== s[end]) return false;
start++;
end--;
}
return true;
};
for (let leftStart = 0; leftStart < n; leftStart++) {
for (let leftEnd = leftStart; leftEnd < n; leftEnd++) {
if ((leftEnd - leftStart + 1) % 2 === 1 && isPalindrome(leftStart, leftEnd)) {
let leftLength = leftEnd - leftStart + 1;
for (let rightStart = leftEnd + 1; rightStart < n; rightStart++) {
for (let rightEnd = rightStart; rightEnd < n; rightEnd++) {
if ((rightEnd - rightStart + 1) % 2 === 1 && isPalindrome(rightStart, rightEnd)) {
let rightLength = rightEnd - rightStart + 1;
maxProduct = Math.max(maxProduct, leftLength * rightLength);
}
}
}
}
}
}
return maxProduct;
}
let s = "zaaaxbbby";
console.log(maxProductEvenPalindromes(s));#include <stdio.h>
#include <string.h>
int maxProductEvenPalindromes(char* s) {
int n = strlen(s);
int maxProduct = 0;
for (int center = 0; center < n; ++center) {
for (int length = 0; center - length >= 0 && center + length < n && s[center - length] == s[center + length]; ++length) {
int leftProduct = 1 + length * 2;
for (int nextCenter = center + length + 1; nextCenter < n; ++nextCenter) {
for (int nextLength = 0; nextCenter - nextLength >= 0 && nextCenter + nextLength < n && s[nextCenter - nextLength] == s[nextCenter + nextLength]; ++nextLength) {
int rightProduct = 1 + nextLength * 2;
int product = leftProduct * rightProduct;
if (product > maxProduct) {
maxProduct = product;
}
}
}
}
}
return maxProduct;
}
int main() {
char s[] = "zaaaxbbby";
printf("%d\n", maxProductEvenPalindromes(s));
return 0;
}using System;
class Program {
static bool IsPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) return false;
}
return true;
}
public static int MaxProductEvenPalindromes(string s) {
int n = s.Length;
int maxProduct = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i; j < n; j++) {
if ((j - i + 1) % 2 == 1 && IsPalindrome(s, i, j)) {
int leftLength = j - i + 1;
for (int k = j + 1; k < n; k++) {
for (int l = k; l < n; l++) {
if ((l - k + 1) % 2 == 1 && IsPalindrome(s, k, l)) {
int rightLength = l - k + 1;
maxProduct = Math.Max(maxProduct, leftLength * rightLength);
}
}
}
}
}
}
return maxProduct;
}
static void Main() {
string s = "zaaaxbbby";
Console.WriteLine(MaxProductEvenPalindromes(s));
}
}Python solution employs the method of expanding around the center, checking for all possible palindromic centers and combining products of lengths of all valid palindromes detected in specific runs over the string.
Time Complexity: O(n^2) as we iterate over every character pair. Space Complexity: O(1), as no extra space is used apart from iteration variables.
Approach 2: Default Approach
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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Expand Around Center for Palindromes | Time Complexity: O(n^2) as we iterate over every character pair. Space Complexity: O(1), as no extra space is used apart from iteration variables. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Palindrome Enumeration | O(n^3) | O(1) | Only for conceptual understanding or very small inputs |
| Expand Around Center with Prefix/Suffix Arrays | O(n^2) | O(n) | Practical interview solution; straightforward to implement |
| Manacher's Algorithm | O(n) | O(n) | Best theoretical performance for large strings |
| Rolling Hash Palindrome Checking | O(n log n) to O(n) | O(n) | Useful when combining substring hashing with other string queries |
Frequently asked questions
Is Maximum Product of the Length of Two Palindromic Substrings easy or hard?
LeetCode classifies this problem as Hard because it combines palindrome detection with non-overlapping interval optimization. A naive approach is simple but inefficient, while optimal solutions require deeper knowledge of string algorithms like Manacher’s algorithm or advanced prefix/suffix preprocessing.
Maximum Product of the Length of Two Palindromic Substrings Python/Java solution
Implement the expand-around-center technique and maintain two arrays: one storing the longest palindrome ending at or before each index and another storing the longest palindrome starting at or after each index. After preprocessing, scan all split points and compute the product of these values. The same logic works in Python, Java, C++, JavaScript, and other languages.
How to solve Maximum Product of the Length of Two Palindromic Substrings in O(n)?
Use Manacher’s algorithm to compute the palindrome radius at every index in linear time. From these radii, derive arrays storing the longest palindrome ending at each position and starting at each position. Iterate over every split between characters and multiply the best left and right palindrome lengths to obtain the maximum product.
What is the best approach for Maximum Product of the Length of Two Palindromic Substrings?
The most practical approach expands palindromes around every center and records the best palindrome ending at each index and starting at each index. After building prefix and suffix arrays, iterate over all split points and compute the product of the best left and right palindrome lengths. This approach runs in O(n^2) time and O(n) space and is commonly accepted in interviews.
Is Maximum Product of the Length of Two Palindromic Substrings asked at Google/Amazon/Meta?
Hard string and palindrome problems of this type frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of palindrome detection, prefix/suffix preprocessing, and advanced string algorithms such as Manacher’s algorithm or rolling hash.
What data structure is used in Maximum Product of the Length of Two Palindromic Substrings?
The solution mainly uses arrays to store prefix and suffix information about the longest palindromes. String processing techniques such as expand-around-center, Manacher’s algorithm, or rolling hash with a hash function are used to detect palindromes efficiently.
What is the time complexity of Maximum Product of the Length of Two Palindromic Substrings?
The typical expand-around-center solution runs in O(n^2) time because each index can expand up to the full string length. Space complexity is O(n) for prefix and suffix arrays storing maximum palindrome lengths. With Manacher’s algorithm, the problem can be optimized to O(n) time and O(n) space.