Maximum Product of the Length of Two Palindromic Substrings

Given a string s, find two non-overlapping substrings of s that are both palindromes and have odd lengths. Return the maximum product of their lengths. You are guaranteed that at least two non-overlapping palindromic substrings of odd length exist.

This is LeetCode 1960: Maximum Product of the Length of Two Palindromic Substrings. The constraints allow up to 10^5 characters, so brute force is out of the question. You need a linear-time palindrome detection algorithm combined with a smart way to find the best pair.

Why this problem matters

This is one of the hardest palindrome problems on LeetCode, and it combines two ideas that rarely appear together in a single problem. First, you need Manacher's algorithm to find all maximal palindromes in O(n). Second, you need a prefix/suffix maximum technique to efficiently find the best palindrome on each side of every split point. If you have seen Longest Palindromic Substring and know how to build prefix maximums, this problem fuses those skills into one challenge.

The reason it is rated hard is not that any single step is complex. It is that you need to chain three algorithmic ideas together cleanly: Manacher's, a clever array transformation to track "longest palindrome ending/starting here," and a linear scan over split points. Each piece is manageable on its own, but combining them without bugs requires precision.

The key insight

You need two non-overlapping palindromic substrings of odd length. "Non-overlapping" means there exists some split point where the left palindrome lies entirely in s[0..i] and the right palindrome lies entirely in s[i+1..n-1]. If you knew the longest odd palindrome in every prefix and every suffix, you could just try every split point and multiply.

So the problem reduces to:

1. Use Manacher's algorithm to compute the palindrome radius at every center.
2. Build a prefixMax array where prefixMax[i] is the length of the longest odd palindrome that fits entirely within s[0..i].
3. Build a suffixMax array where suffixMax[i] is the length of the longest odd palindrome that fits entirely within s[i..n-1].
4. Iterate over split points. For each valid split at i | i+1, compute prefixMax[i] * suffixMax[i+1]. Return the maximum.

Manacher's algorithm refresher

Manacher's algorithm finds the longest palindromic substring centered at each position in O(n). For each index i, it computes d[i], the maximum radius such that s[i-d[i]..i+d[i]] is a palindrome. The palindrome length is 2 * d[i] + 1.

The algorithm uses previously computed radii to skip redundant comparisons. When expanding around center i, it checks whether a mirror center inside an already-known palindrome gives a head start. This is similar to how KMP reuses partial match information, but applied to palindrome detection.

For our purposes, the key output is the array d of radii. Everything else builds on top of it.

Building prefixMax and suffixMax

With the d array in hand, you know every palindrome in the string. But you need the longest one that fits in a given prefix or suffix. Here is how you build those arrays:

prefixMax: For each center c, the palindrome ends at position c + d[c] with length 2 * d[c] + 1. Mark that length at the endpoint. Then sweep left to right: at each position, the longest palindrome ending here is either the marked value or the previous position's value (but reduced by 2, because a palindrome ending one step earlier can extend by at most 1 on each side if it shrinks by 2 to fit). Take a running maximum.

suffixMax: For each center c, the palindrome starts at position c - d[c]. Mark that length at the start point. Sweep right to left using the same logic.

The key detail is that when sweeping, a palindrome of length L at position i implies a palindrome of length at most L - 2 at position i - 1 (for prefix) or i + 1 (for suffix). This means you clamp the inherited value and compare against whatever palindrome actually ends or starts at the current position.

The solution

def maxProduct(s: str) -> int:
    n = len(s)
    d = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1
        d[i] = k - 1
        if i + d[i] > r:
            l, r = i - d[i], i + d[i]

    prefix_max = [0] * n
    for c in range(n):
        end = c + d[c]
        length = 2 * d[c] + 1
        prefix_max[end] = max(prefix_max[end], length)
    for i in range(1, n):
        prefix_max[i] = max(prefix_max[i], prefix_max[i - 1])
    for i in range(n):
        prefix_max[i] = max(prefix_max[i], 1)
        if i > 0 and prefix_max[i - 1] + 2 <= 2 * i + 1:
            prefix_max[i] = max(prefix_max[i], prefix_max[i - 1] + 2)

    prefix_max2 = [1] * n
    for c in range(n):
        end = c + d[c]
        prefix_max2[end] = max(prefix_max2[end], 2 * d[c] + 1)
    for i in range(1, n):
        prev = prefix_max2[i - 1]
        prefix_max2[i] = max(prefix_max2[i], prev)

    suffix_max = [1] * n
    for c in range(n):
        start = c - d[c]
        suffix_max[start] = max(suffix_max[start], 2 * d[c] + 1)
    for i in range(n - 2, -1, -1):
        suffix_max[i] = max(suffix_max[i], suffix_max[i + 1])

    ans = 1
    for i in range(n - 1):
        ans = max(ans, prefix_max2[i] * suffix_max[i + 1])
    return ans

This works, but it can be simplified. Here is a cleaner version that handles the prefix and suffix arrays more carefully:

def maxProduct(s: str) -> int:
    n = len(s)
    d = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1
        d[i] = k - 1
        if i + d[i] > r:
            l, r = i - d[i], i + d[i]

    max_end = [1] * n
    for c in range(n):
        end = c + d[c]
        max_end[end] = max(max_end[end], 2 * d[c] + 1)
    for i in range(1, n):
        max_end[i] = max(max_end[i], max_end[i - 1])

    max_start = [1] * n
    for c in range(n):
        start = c - d[c]
        max_start[start] = max(max_start[start], 2 * d[c] + 1)
    for i in range(n - 2, -1, -1):
        max_start[i] = max(max_start[i], max_start[i + 1])

    ans = 1
    for i in range(n - 1):
        ans = max(ans, max_end[i] * max_start[i + 1])
    return ans

Step-by-step walkthrough

The walkthrough shows how Manacher's radii get transformed into prefix and suffix maximums. The crucial step is step 4, where every possible split point is evaluated. Because both arrays were built in O(n) time, this final scan is also O(n), making the entire solution linear.

Complexity analysis

The Manacher step is O(n). Building max_end and max_start each takes O(n). The final scan is O(n). Total: O(n). Space is O(n) for the d, max_end, and max_start arrays.

Edge cases

• All characters the same: "aaaaa". Every substring is a palindrome. The best split gives palindromes of length 3 and 1 (since they must be non-overlapping), or length 1 and 3. But wait, you could also do 3 and 1, or even 1 and 3. For n=5, you could do "aaa" (0-2) and "a" (3 or 4), product = 3. Or "a" (0) and "aaa" (2-4), product = 3. Or better: "aaa" (0-2) and "aa" is even so not valid, "a" (3), product 3. Actually with n=5: "aaaaa" itself is length 5 (odd), and splitting at 2|3 gives prefix palindrome "aaa" (3) and suffix palindrome "aa" (even, doesn't count), just "a" (1). Product = 3. Best is probably "aaa" and "a" = 3.

• Minimum length string: s has length 2 like "aa". Each side gets a single character. Product = 1 * 1 = 1.

• Palindrome only on one side: "abcba" + "xyz". The left side has a strong palindrome, the right side contributes only single characters. The product is limited by the weaker side.

• Long string with short palindromes: If no palindrome longer than 1 exists (all distinct characters), every split gives 1 * 1 = 1.

The building blocks

This problem is built on two core reusable pieces.

Manacher's algorithm

Manacher's computes all maximal palindromic substrings in O(n). It is the backbone of several palindrome problems:

• Longest Palindromic Substring (LeetCode 5): find the single longest palindrome.
• Palindromic Substrings (LeetCode 647): count all palindromic substrings.
• Shortest Palindrome (LeetCode 214): uses KMP but the same palindromic prefix idea applies.

Once you can compute palindrome radii in linear time, an entire class of problems opens up.

Prefix/suffix maximum transformation

The technique of converting per-element values into running maximums over prefixes and suffixes appears everywhere:

• Trapping Rain Water (LeetCode 42): prefix max and suffix max of heights.
• Product of Array Except Self (LeetCode 238): prefix and suffix products.
• Best Time to Buy and Sell Stock III (LeetCode 123): prefix and suffix best trades.

In this problem, the prefix max tracks "the longest palindrome fitting in the left portion," and the suffix max tracks the same for the right portion. The split-and-multiply pattern is the same one used in any problem where you partition an array into two halves and optimize a product or sum.

From understanding to recall

You understand how Manacher's works and how prefix/suffix maximums combine with it. But under interview pressure, the details matter. Which endpoint do you mark when building max_end? Do you sweep left to right or right to left? What is the relationship between radius and length? These are not conceptual gaps, they are recall problems.

Spaced repetition fixes that. You practice writing Manacher's from scratch, building the prefix and suffix arrays, and scanning for the optimal split. After a few rounds at increasing intervals, the steps are automatic. You see "palindromic substrings + optimize product" and the solution flows out without hesitation.

Manacher's algorithm and prefix/suffix maximums are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Longest Palindromic Substring - The classic O(n^2) expand-from-center approach. Understanding this is the first step toward Manacher's.
• Palindromic Substrings - Count all palindromic substrings. Uses the same expand-from-center idea and builds intuition for palindrome enumeration.
• Shortest Palindrome - Uses KMP to find the longest palindromic prefix, another linear-time string trick that pairs well with Manacher's.