Skip to main content
Talentd

Maximum Product of the Length of Two Palindromic Substrings - Solution & Explanation

HardStringRolling HashHash Function13 min read
Practice this problem

Problem Statement

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 <= 105
  • s consists 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.

This solution loops through each character of the string and treat it as a potential center of a palindrome, expanding outward to find all palindromic substrings. It checks products of lengths of all valid palindromes and stores the maximum product encountered.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) due to nested loops for finding palindromes and computing products. Space Complexity: O(1), as no extra space is used except for variables.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Expand Around Center for Palindromes

Time Complexity: O(n^3) due to nested loops for finding palindromes and computing products. Space Complexity: O(1), as no extra space is used except for variables.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Palindrome EnumerationO(n^3)O(1)Only for conceptual understanding or very small inputs
Expand Around Center with Prefix/Suffix ArraysO(n^2)O(n)Practical interview solution; straightforward to implement
Manacher's AlgorithmO(n)O(n)Best theoretical performance for large strings
Rolling Hash Palindrome CheckingO(n log n) to O(n)O(n)Useful when combining substring hashing with other string queries

Video Solution

LeetCode 1960. Maximum Product of the Length of Two Palindromic Substrings • Happy Coding • 1,799 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Product of the Length of Two Palindromic Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Product of the Length of Two Palindromic Subsequences

Next

Minimum Cost to Make Array Equal