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.The goal in #1960 Maximum Product of the Length of Two Palindromic Substrings is to choose two non‑overlapping palindromic substrings such that the product of their lengths is maximized. A key observation is that the string can be split into a left and right part, where the best palindrome lies entirely in each side.
One efficient strategy uses rolling hash to check whether a substring is a palindrome in O(1) time after preprocessing. By combining prefix and reverse hash arrays, we can binary search around each center to find the longest palindromic substring ending or starting at each index. We maintain arrays that store the best palindrome length up to every prefix and suffix.
Finally, iterate through all split points and compute the product of the best palindrome on the left and the best palindrome on the right. The maximum value across all splits gives the answer. This approach avoids brute force checks and scales efficiently for large strings.
Time complexity is typically O(n log n) with binary search and hashing, while space complexity is O(n) for hash and helper arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Rolling Hash + Binary Search for Palindromes | O(n log n) | O(n) |
| Manacher-based Optimization | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You can use Manacher's algorithm to get the maximum palindromic substring centered at each index
After using Manacher's for each center use a line sweep from the center to the left and from the center to the right to find for each index the farthest center to it with distance ≤ palin[center]
After that, find the maximum palindrome size for each prefix in the string and for each suffix and the answer would be max(prefix[i] * suffix[i + 1])
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Hard string problems involving palindromes, hashing, and substring optimization are common in FAANG-style interviews. This problem tests knowledge of advanced palindrome techniques like Manacher’s algorithm and rolling hash.
Rolling hash structures are often used to verify palindromes in constant time after preprocessing. Combined with prefix and suffix arrays, they allow efficient tracking of the longest palindromic substrings around each position.
Yes, Manacher’s algorithm can compute all palindromic radii in linear time. Using these radii, you can derive the longest palindrome ending or starting at each index and evaluate split points to maximize the product.
A common optimal strategy is to precompute palindromic ranges using rolling hash or Manacher’s algorithm. Then maintain prefix and suffix arrays storing the longest palindrome ending or starting at each position. By evaluating every split point, you can maximize the product of two non-overlapping palindromes efficiently.