# Maximum Product of the Length of Two Palindromic Substrings
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-the-length-of-two-palindromic-substrings
**Patterns:** [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String
---
## Problem
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 <= 105`
* `s` consists of lowercase English letters.

# Approaches
## Brute Force with Split Point
This approach considers every possible way to split the string into two non-empty, non-overlapping substrings. For each split, it exhaustively searches for the longest odd-length palindrome in the left substring and the longest odd-length palindrome in the right substring. The product of these two lengths is a candidate for the maximum product.
**Time:** O(n^3), where n is the length of the string. The outer loop runs `n` times for the split point. Inside, finding the max palindrome takes O(length^2), leading to a total of `Sum(p^2 + (n-p)^2)` for `p` from 1 to `n-1`, which is O(n^3). · **Space:** O(1)
**Pros:** Simple to conceptualize and implement.; Correctly models the problem of non-intersecting substrings.
**Cons:** Extremely inefficient due to nested loops and repeated computations.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The core idea is to iterate through every possible index `p` that can serve as a boundary between the two palindromic substrings. For a given `p`, one palindrome must lie entirely within `s[0...p-1]` and the other entirely within `s[p...n-1]`. 

For each such partition, we need to find the maximum possible length of an odd-length palindrome on the left side and on the right side. This is done by a helper function, `findMaxOddPalindrome`, which iterates through all possible centers in a given substring and expands outwards to find the longest palindrome for each center. This process is computationally expensive because for each of the `n-1` splits, we perform a search that takes roughly `O(p^2)` for the left part and `O((n-p)^2)` for the right part, leading to an overall cubic time complexity.

```java
class Solution {
    public long maxProduct(String s) {
        int n = s.length();
        if (n < 2) {
            return 0;
        }
        long maxProd = 0;

        for (int i = 1; i < n; i++) {
            long leftMax = findMaxOddPalindrome(s, 0, i - 1);
            long rightMax = findMaxOddPalindrome(s, i, n - 1);
            if (leftMax > 0 && rightMax > 0) {
                maxProd = Math.max(maxProd, leftMax * rightMax);
            }
        }
        return maxProd;
    }

    private int findMaxOddPalindrome(String s, int start, int end) {
        int maxLen = 0;
        for (int i = start; i <= end; i++) {
            // Expand from center i
            int l = i, r = i;
            while (l >= start && r <= end && s.charAt(l) == s.charAt(r)) {
                maxLen = Math.max(maxLen, r - l + 1);
                l--;
                r++;
            }
        }
        // If no palindrome is found, every single character is a palindrome of length 1.
        return maxLen > 0 ? maxLen : (end >= start ? 1 : 0);
    }
}
```
### Algorithm
- Initialize a variable `max_product` to 0.
- Iterate through all possible split points `p` from `1` to `s.length() - 1`.
- For each split point `p`, the string is divided into two parts: a left part `s[0...p-1]` and a right part `s[p...s.length()-1]`.
- Find the maximum length of an odd-length palindrome in the left part (`max_len_left`).
  - To do this, iterate through every character in the left part as a potential center.
  - For each center, expand outwards to find the longest palindrome and keep track of the maximum length found.
- Find the maximum length of an odd-length palindrome in the right part (`max_len_right`) using the same expansion method.
- If both `max_len_left` and `max_len_right` are greater than 0, calculate their product.
- Update `max_product = max(max_product, max_len_left * max_len_right)`.
- After checking all split points, return `max_product`.

## Precomputation with Expand from Center
This approach improves upon the brute-force method by avoiding redundant calculations. Instead of re-calculating the longest palindrome for every possible substring split, we first precompute the lengths of all odd-length palindromes centered at every character in the string. This is done using the 'expand from center' technique. With this information, we can then efficiently build two arrays: one for the maximum palindrome length in any prefix `s[0...i]` and another for any suffix `s[i...n-1]`. Finally, we iterate through all split points and use our precomputed arrays to find the maximum product in linear time.
**Time:** O(n^2), where n is the length of the string. The precomputation of palindrome radii using 'expand from center' for all centers dominates the runtime. · **Space:** O(n) for storing the `radii`, `left_max`, and `right_max` arrays.
**Pros:** Much more efficient than the pure brute-force approach.; Introduces the powerful idea of precomputation and dynamic programming.; The logic for combining results is efficient (O(n)).
**Cons:** The O(n^2) precomputation step is the bottleneck.; This approach is too slow for the given constraints (n <= 10^5) and will time out.
### Explanation
The main bottleneck in the previous approach was the repeated O(n^2) search for palindromes. We can optimize this by doing the search just once. 

1.  **Precomputation:** We create an array, say `radii`, of the same size as the string. `radii[i]` will store the radius of the longest odd-length palindrome centered at `s[i]`. We can populate this array by iterating through each index `i` and expanding outwards (`l=i-1, r=i+1`) as long as `s[l] == s[r]`. This whole precomputation step takes O(n^2) time.

2.  **DP Arrays:** We then use this `radii` array to build `left_max` and `right_max` arrays. 
    - `left_max[i]` stores the maximum length of a palindrome in `s[0...i]`. It can be computed as `left_max[i] = max(left_max[i-1], max length of any palindrome ending at i)`. 
    - `right_max[i]` stores the maximum length of a palindrome in `s[i...n-1]`. It can be computed as `right_max[i] = max(right_max[i+1], max length of any palindrome starting at i)`.

3.  **Final Calculation:** With `left_max` and `right_max` arrays ready, we can find the answer by iterating through all `n-1` split points. For a split between `i` and `i+1`, the answer is `left_max[i] * right_max[i+1]`. We take the maximum over all `i`.

```java
class Solution {
    public long maxProduct(String s) {
        int n = s.length();
        if (n < 2) return 0;

        // Step 1: Precompute radii for all odd-length palindromes (O(n^2))
        int[] radii = new int[n];
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                radii[i] = r - i;
                l--;
                r++;
            }
        }

        // Step 2 & 3: Compute left_max and right_max arrays
        int[] left_max = new int[n];
        int[] right_max = new int[n];
        Arrays.fill(left_max, 1);
        Arrays.fill(right_max, 1);

        for (int i = 0; i < n; i++) {
            int len = 2 * radii[i] + 1;
            left_max[i + radii[i]] = Math.max(left_max[i + radii[i]], len);
            right_max[i - radii[i]] = Math.max(right_max[i - radii[i]], len);
        }

        // Create prefix and suffix max arrays
        for (int i = 1; i < n; i++) {
            left_max[i] = Math.max(left_max[i], left_max[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            right_max[i] = Math.max(right_max[i], right_max[i + 1]);
        }

        // Step 4: Calculate max product
        long maxProd = 0;
        for (int i = 0; i < n - 1; i++) {
            maxProd = Math.max(maxProd, (long)left_max[i] * right_max[i + 1]);
        }

        return maxProd;
    }
}
```
### Algorithm
- **Step 1: Precompute Palindrome Radii.** Create an array `radii` of size `n`. For each index `i` from `0` to `n-1`, calculate the radius of the longest odd-length palindrome centered at `i` by expanding outwards. Store this in `radii[i]`. This step takes O(n^2).
- **Step 2: Compute Prefix Maximums.** Create an array `left_max` of size `n`. `left_max[i]` will store the maximum length of an odd-length palindrome contained entirely in the prefix `s[0...i]`. This can be computed in O(n) using the `radii` array.
- **Step 3: Compute Suffix Maximums.** Create an array `right_max` of size `n`. `right_max[i]` will store the maximum length of an odd-length palindrome contained entirely in the suffix `s[i...n-1]`. This can also be computed in O(n) using the `radii` array.
- **Step 4: Calculate Maximum Product.** Iterate from `i = 0` to `n-2`. For each `i`, consider the split between `i` and `i+1`. The maximum product for this split is `left_max[i] * right_max[i+1]`. Keep track of the overall maximum product found.
- **Step 5: Return** the final maximum product.

## Linear Time Solution using Manacher's Algorithm
This is the most optimal approach, achieving linear time complexity. It builds upon the previous dynamic programming idea but replaces the O(n^2) 'expand from center' precomputation with the highly efficient Manacher's algorithm. Manacher's algorithm can find the lengths of all palindromes centered at each position in O(n) time. Once we have these lengths, the rest of the logic—building the prefix-max and suffix-max length arrays and then combining the results—remains the same and also runs in O(n), leading to an overall linear time solution.
**Time:** O(n), where n is the length of the string. Each step (Manacher's, DP array construction, final product calculation) takes linear time. · **Space:** O(n) to store the radii array from Manacher's algorithm and the two DP arrays (`left` and `right`).
**Pros:** Optimal time complexity of O(n), making it very fast for large inputs.; Efficiently solves the problem by combining a powerful algorithm (Manacher's) with dynamic programming.
**Cons:** The implementation is more complex due to Manacher's algorithm.; Requires careful handling of indices and array updates.
### Explanation
The key to achieving a linear time solution is to optimize the palindrome discovery step. Manacher's algorithm is perfect for this. A simplified version tailored for odd-length palindromes can determine the radius of the longest palindrome centered at each character `s[i]` in O(n) time.

**Algorithm Steps:**
1.  **Manacher's for Odd Palindromes:** We compute an array `d` where `d[i]` is the radius of the longest odd-length palindrome centered at `i`. This is done by intelligently reusing information from previously found palindromes to avoid redundant character comparisons.

2.  **DP Arrays Construction:** We create two arrays, `left` and `right`, of size `n`. 
    - `left[i]` will store the max length of a palindrome ending at or before index `i`.
    - `right[i]` will store the max length of a palindrome starting at or after index `i`.
    We first populate these arrays at specific indices. For a palindrome centered at `c` with radius `r`, its length is `2*r+1`. It starts at `c-r` and ends at `c+r`. So we set `right[c-r] = max(right[c-r], 2*r+1)` and `left[c+r] = max(left[c+r], 2*r+1)`. After iterating through all centers, we perform a prefix-max scan on `left` and a suffix-max scan on `right` to fill in the remaining values.

3.  **Combine and Conquer:** Finally, we iterate through all possible split points `i` from `0` to `n-2`. The two non-intersecting palindromes are chosen from `s[0...i]` and `s[i+1...n-1]`. The maximum product for this split is `left[i] * right[i+1]`. We find the maximum product over all possible splits.

```java
class Solution {
    public long maxProduct(String s) {
        int n = s.length();
        if (n < 2) {
            return 0;
        }

        // Step 1: Manacher's algorithm for odd length palindromes -> O(n)
        int[] d = new int[n]; // d[i] = radius of palindrome centered at i
        int l = 0, r = -1; // [l, r] is the rightmost palindrome found so far
        for (int i = 0; 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 - 1;
            if (i + d[i] > r) {
                l = i - d[i];
                r = i + d[i];
            }
        }

        // Step 2 & 3: Compute left and right max arrays -> O(n)
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);

        for (int i = 0; i < n; i++) {
            int len = 2 * d[i] + 1;
            left[i + d[i]] = Math.max(left[i + d[i]], len);
            right[i - d[i]] = Math.max(right[i - d[i]], len);
        }

        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i], left[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i], right[i + 1]);
        }

        // Step 4: Calculate max product -> O(n)
        long maxProd = 0;
        for (int i = 0; i < n - 1; i++) {
            maxProd = Math.max(maxProd, (long)left[i] * right[i + 1]);
        }

        return maxProd;
    }
}
```
### Algorithm
- **Step 1: Compute Palindrome Radii with Manacher's Algorithm.** Use a simplified version of Manacher's algorithm to find the radius of the longest odd-length palindrome centered at each index `i`. This computes a `radii` array of size `n` in O(n) time.
- **Step 2: Populate Max Lengths at End/Start Points.** Initialize two arrays, `left_max` and `right_max`, of size `n` with 1s. Iterate from `i = 0` to `n-1`. For each center `i`, find its palindrome's length `len = 2*radii[i]+1`, start index `s = i-radii[i]`, and end index `e = i+radii[i]`. Update `left_max[e] = max(left_max[e], len)` and `right_max[s] = max(right_max[s], len)`.
- **Step 3: Compute Prefix and Suffix Maximums.**
  - Perform a prefix-max scan on `left_max`: for `i` from 1 to `n-1`, `left_max[i] = max(left_max[i], left_max[i-1])`. Now, `left_max[i]` stores the max palindrome length in `s[0...i]`.
  - Perform a suffix-max scan on `right_max`: for `i` from `n-2` down to `0`, `right_max[i] = max(right_max[i], right_max[i+1])`. Now, `right_max[i]` stores the max palindrome length in `s[i...n-1]`.
- **Step 4: Calculate Final Maximum Product.** Initialize `max_product = 0`. Iterate from `i = 0` to `n-2` and update `max_product = max(max_product, (long)left_max[i] * right_max[i+1])`.
- **Step 5: Return** `max_product`.

# Solutions
### Java

```java
class Solution {
public
  long maxProduct(String s) {
    int length = s.length();
    int[] span = new int[length];
    for (int i = 0, l = 0, r = -1; i < length; i++) {
      span[i] = i <= r ? Math.min(span[l + r - i], r - i + 1) : 1;
      while (i - span[i] >= 0 && i + span[i] < length &&
             s.charAt(i - span[i]) == s.charAt(i + span[i]))
        span[i]++;
      if (i + span[i] - 1 > r) {
        l = i - span[i] + 1;
        r = i + span[i] - 1;
      }
    }
    int[] pre = new int[length];
    int[] suf = new int[length];
    for (int i = 0; i < length; i++) {
      pre[i + span[i] - 1] = Math.max(pre[i + span[i] - 1], span[i] * 2 - 1);
      suf[i - span[i] + 1] = Math.max(suf[i - span[i] + 1], span[i] * 2 - 1);
    }
    for (int i = 1; i < length; i++)
      pre[i] = Math.max(pre[i], pre[i - 1]);
    for (int i = length - 2; i >= 0; i--)
      pre[i] = Math.max(pre[i], pre[i + 1] - 2);
    for (int i = length - 2; i >= 0; i--)
      suf[i] = Math.max(suf[i], suf[i + 1]);
    for (int i = 1; i < length; i++)
      suf[i] = Math.max(suf[i], suf[i - 1] - 2);
    long product = 0;
    for (int i = 0; i < length - 1; i++)
      product = Math.max(product, (long)pre[i] * suf[i + 1]);
    return product;
  }
}

```