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.

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.

Description Hints 3 Solution Video 30:14

1960. Maximum Product of the Length of Two Palindromic Substrings

Q: 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.

Q: 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.

Hard32.1% acceptance

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 <= 10⁵
s consists of lowercase English letters.

Topics

Hints open one at a time

Hint 1

You can use Manacher's algorithm to get the maximum palindromic substring centered at each index

Hint 2

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]

Hint 3

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])

30:14

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

1960. Maximum Product of the Length of Two Palindromic Substrings

Topics

Hints open one at a time

Similar problems