Problem statement

Given a string s, choose two non-overlapping palindromic substrings, both of odd length, and return the maximum possible product of their lengths.

Formally, pick indices i <= j < k <= l such that s[i..j] and s[k..l] are palindromes and j - i + 1 and l - k + 1 are odd; maximise (j - i + 1) * (l - k + 1).

A palindrome reads the same forwards and backwards.

Example 1

Input: s = "kayakaba"
Output: 15
Explanation: `"kayak"` (length 5) and `"aba"` (length 3) do not overlap.

Example 2

Input: s = "racecarlevel"
Output: 35
Explanation: `"racecar"` × `"level"` = 7 × 5.

Example 3

Input: s = "ab"
Output: 1
Explanation: Two single letters.

Constraints

• 2 <= s.length <= 9 * 10^4 (LeetCode allows 10^5; capped so the product fits a 32-bit integer)
• s consists of lowercase English letters

Hints for Maximum Product of the Length of Two Palindromic Substrings

1. Hint 1

   Split the string at a boundary: the answer is the best odd palindrome entirely left of it times the best one entirely right of it, maximised over all boundaries.

2. Hint 2

   Manacher's algorithm gives, for every centre, the radius of the longest odd palindrome around it in O(n) total.

3. Hint 3

   A palindrome of length L ending at e also gives one of length L - 2 ending at e - 1. Mark each centre's longest palindrome at its end, sweep right-to-left with -2, then take prefix maxima; do the mirror for starts.

How to solve Maximum Product of the Length of Two Palindromic Substrings

Compute pref[i] = the longest odd palindrome inside s[0..i] and suf[i] = the longest inside s[i..n-1]; the answer is max pref[i] · suf[i + 1]. Manacher's radii make both arrays linear.

Approach

1. Run Manacher's odd-length pass: d[i] is the number of characters on each side of centre i (counting i), so the palindrome there has length 2·d[i] - 1.
2. For each centre set pref[i + d[i] - 1] = max(…, 2·d[i] - 1) and suf[i - d[i] + 1] = max(…, 2·d[i] - 1).
3. Sweep pref from right to left with pref[i] = max(pref[i], pref[i + 1] - 2), then left to right with prefix maxima. Mirror both sweeps for suf.
4. Return the maximum of pref[i] · suf[i + 1] over 0 <= i < n - 1, using 64-bit arithmetic for the product.

Why it works

Two non-overlapping substrings are separated by some boundary between i and i + 1, and for a fixed boundary the best choice on each side is independent. Trimming one character from each end of an odd palindrome leaves an odd palindrome, which is what the -2 sweeps propagate: after them, pref[e] is the longest odd palindrome ending exactly at e, and the prefix maxima extend it to anything ending at or before e.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Only the longest palindrome per centre is recorded; shorter palindromes ending later than another centre's are recovered only by the -2 sweep — skipping it gives wrong answers.
• Both palindromes must have odd length; even palindromes such as "bb" do not count.
• The product can exceed 2^31 - 1 on LeetCode's full limits; compute it in 64 bits.

Reference solution

Python

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
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    pref = [0] * n
    suf = [0] * n
    for i in range(n):
        length = 2 * d[i] - 1
        e = i + d[i] - 1
        b = i - d[i] + 1
        if length > pref[e]:
            pref[e] = length
        if length > suf[b]:
            suf[b] = length
    for i in range(n - 2, -1, -1):
        pref[i] = max(pref[i], pref[i + 1] - 2)
    for i in range(1, n):
        pref[i] = max(pref[i], pref[i - 1])
    for i in range(1, n):
        suf[i] = max(suf[i], suf[i - 1] - 2)
    for i in range(n - 2, -1, -1):
        suf[i] = max(suf[i], suf[i + 1])
    return max(pref[i] * suf[i + 1] for i in range(n - 1))

Java

public static int maxProduct(String s) {
    int n = s.length();
    int[] d = new int[n];
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = i > r ? 1 : Math.min(d[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s.charAt(i - k) == s.charAt(i + k)) k++;
        d[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    int[] pref = new int[n], suf = new int[n];
    for (int i = 0; i < n; i++) {
        int len = 2 * d[i] - 1;
        pref[i + d[i] - 1] = Math.max(pref[i + d[i] - 1], len);
        suf[i - d[i] + 1] = Math.max(suf[i - d[i] + 1], len);
    }
    for (int i = n - 2; i >= 0; i--) pref[i] = Math.max(pref[i], pref[i + 1] - 2);
    for (int i = 1; i < n; i++) pref[i] = Math.max(pref[i], pref[i - 1]);
    for (int i = 1; i < n; i++) suf[i] = Math.max(suf[i], suf[i - 1] - 2);
    for (int i = n - 2; i >= 0; i--) suf[i] = Math.max(suf[i], suf[i + 1]);
    long best = 0;
    for (int i = 0; i + 1 < n; i++) best = Math.max(best, (long) pref[i] * suf[i + 1]);
    return (int) best;
}

C++

int maxProduct(string s) {
    int n = s.size();
    vector<int> d(n, 0);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = i > r ? 1 : min(d[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
        d[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    vector<int> pref(n, 0), suf(n, 0);
    for (int i = 0; i < n; i++) {
        int len = 2 * d[i] - 1;
        pref[i + d[i] - 1] = max(pref[i + d[i] - 1], len);
        suf[i - d[i] + 1] = max(suf[i - d[i] + 1], len);
    }
    for (int i = n - 2; i >= 0; i--) pref[i] = max(pref[i], pref[i + 1] - 2);
    for (int i = 1; i < n; i++) pref[i] = max(pref[i], pref[i - 1]);
    for (int i = 1; i < n; i++) suf[i] = max(suf[i], suf[i - 1] - 2);
    for (int i = n - 2; i >= 0; i--) suf[i] = max(suf[i], suf[i + 1]);
    long long best = 0;
    for (int i = 0; i + 1 < n; i++) best = max(best, (long long) pref[i] * suf[i + 1]);
    return (int) best;
}

JavaScript

var maxProduct = function(s) {
    var n = s.length, d = new Array(n).fill(0), l = 0, r = -1, i;
    for (i = 0; i < n; i++) {
        var k = i > r ? 1 : Math.min(d[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] === s[i + k]) k++;
        d[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    var pref = new Array(n).fill(0), suf = new Array(n).fill(0);
    for (i = 0; i < n; i++) {
        var len = 2 * d[i] - 1, e = i + d[i] - 1, b = i - d[i] + 1;
        if (len > pref[e]) pref[e] = len;
        if (len > suf[b]) suf[b] = len;
    }
    for (i = n - 2; i >= 0; i--) pref[i] = Math.max(pref[i], pref[i + 1] - 2);
    for (i = 1; i < n; i++) pref[i] = Math.max(pref[i], pref[i - 1]);
    for (i = 1; i < n; i++) suf[i] = Math.max(suf[i], suf[i - 1] - 2);
    for (i = n - 2; i >= 0; i--) suf[i] = Math.max(suf[i], suf[i + 1]);
    var best = 0;
    for (i = 0; i + 1 < n; i++) best = Math.max(best, pref[i] * suf[i + 1]);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard
• Find the Original Typed String II Hard