Watch 4 video solutions for Maximum Product of the Length of Two Palindromic Substrings, a hard level problem involving String, Rolling Hash, Hash Function. This walkthrough by Happy Coding has 1,768 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 | 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 |