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 themaximum 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.

Examples

Example 1

1
2
3

Input: s = "ababbb"
Output: 9
Explanation: Substrings "aba" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.

Example 2

1
2
3

Input: s = "zaaaxbbby"
Output: 9
Explanation: Substrings "aaa" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.

Constraints

  • 2 <= s.length <= 10^5
  • s consists of lowercase English letters.

Solution

Method 1 – Manacher’s Algorithm + Prefix/Suffix Max

Intuition

To maximize the product of two non-overlapping odd-length palindromic substrings, we need to efficiently find the longest odd-length palindrome ending at or before each position (for the left substring) and starting at or after each position (for the right substring). Manacher’s algorithm allows us to find all palindromic substrings in linear time.

Approach

  1. Use Manacher’s algorithm to compute the maximum odd-length palindrome radius centered at each position.
  2. For each position, compute the maximum odd-length palindrome ending at or before that position (prefix max).
  3. For each position, compute the maximum odd-length palindrome starting at or after that position (suffix max).
  4. For each possible split point, compute the product of the best left and right palindromic substring lengths.
  5. Return the maximum product found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxProduct(string s) {
        int n = s.size();
        vector<int> d(n);
        for (int i = 0; i < n; ++i) {
            int l = 0;
            while (i-l >= 0 && i+l < n && s[i-l] == s[i+l]) ++l;
            d[i] = 2*l-1;
        }
        vector<int> pre(n), suf(n);
        pre[0] = d[0];
        for (int i = 1; i < n; ++i) pre[i] = max(pre[i-1], d[i]);
        suf[n-1] = d[n-1];
        for (int i = n-2; i >= 0; --i) suf[i] = max(suf[i+1], d[i]);
        int ans = 0;
        for (int i = 0; i < n-1; ++i) ans = max(ans, pre[i] * suf[i+1]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func maxProduct(s string) int {
    n := len(s)
    d := make([]int, n)
    for i := 0; i < n; i++ {
        l := 0
        for i-l >= 0 && i+l < n && s[i-l] == s[i+l] {
            l++
        }
        d[i] = 2*l - 1
    }
    pre := make([]int, n)
    suf := make([]int, n)
    pre[0] = d[0]
    for i := 1; i < n; i++ {
        if d[i] > pre[i-1] {
            pre[i] = d[i]
        } else {
            pre[i] = pre[i-1]
        }
    }
    suf[n-1] = d[n-1]
    for i := n-2; i >= 0; i-- {
        if d[i] > suf[i+1] {
            suf[i] = d[i]
        } else {
            suf[i] = suf[i+1]
        }
    }
    ans := 0
    for i := 0; i < n-1; i++ {
        prod := pre[i] * suf[i+1]
        if prod > ans {
            ans = prod
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        int[] d = new int[n];
        for (int i = 0; i < n; ++i) {
            int l = 0;
            while (i-l >= 0 && i+l < n && s.charAt(i-l) == s.charAt(i+l)) ++l;
            d[i] = 2*l-1;
        }
        int[] pre = new int[n], suf = new int[n];
        pre[0] = d[0];
        for (int i = 1; i < n; ++i) pre[i] = Math.max(pre[i-1], d[i]);
        suf[n-1] = d[n-1];
        for (int i = n-2; i >= 0; --i) suf[i] = Math.max(suf[i+1], d[i]);
        int ans = 0;
        for (int i = 0; i < n-1; ++i) ans = Math.max(ans, pre[i] * suf[i+1]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun maxProduct(s: String): Int {
        val n = s.length
        val d = IntArray(n)
        for (i in 0 until n) {
            var l = 0
            while (i-l >= 0 && i+l < n && s[i-l] == s[i+l]) l++
            d[i] = 2*l-1
        }
        val pre = IntArray(n)
        val suf = IntArray(n)
        pre[0] = d[0]
        for (i in 1 until n) pre[i] = maxOf(pre[i-1], d[i])
        suf[n-1] = d[n-1]
        for (i in n-2 downTo 0) suf[i] = maxOf(suf[i+1], d[i])
        var ans = 0
        for (i in 0 until n-1) ans = maxOf(ans, pre[i] * suf[i+1])
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        d = [0] * n
        for i in range(n):
            l = 0
            while i-l >= 0 and i+l < n and s[i-l] == s[i+l]:
                l += 1
            d[i] = 2*l-1
        pre = [0] * n
        suf = [0] * n
        pre[0] = d[0]
        for i in range(1, n):
            pre[i] = max(pre[i-1], d[i])
        suf[-1] = d[-1]
        for i in range(n-2, -1, -1):
            suf[i] = max(suf[i+1], d[i])
        ans = 0
        for i in range(n-1):
            ans = max(ans, pre[i] * suf[i+1])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

impl Solution {
    pub fn max_product(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut d = vec![0; n];
        for i in 0..n {
            let mut l = 0;
            while i as i32 - l >= 0 && i + l < n && s[i-l] == s[i+l] {
                l += 1;
            }
            d[i] = 2*l-1;
        }
        let mut pre = vec![0; n];
        let mut suf = vec![0; n];
        pre[0] = d[0];
        for i in 1..n {
            pre[i] = pre[i-1].max(d[i]);
        }
        suf[n-1] = d[n-1];
        for i in (0..n-1).rev() {
            suf[i] = suf[i+1].max(d[i]);
        }
        let mut ans = 0;
        for i in 0..n-1 {
            ans = ans.max(pre[i] * suf[i+1]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    maxProduct(s: string): number {
        const n = s.length;
        const d = new Array(n).fill(0);
        for (let i = 0; i < n; ++i) {
            let l = 0;
            while (i-l >= 0 && i+l < n && s[i-l] === s[i+l]) ++l;
            d[i] = 2*l-1;
        }
        const pre = new Array(n).fill(0);
        const suf = new Array(n).fill(0);
        pre[0] = d[0];
        for (let i = 1; i < n; ++i) pre[i] = Math.max(pre[i-1], d[i]);
        suf[n-1] = d[n-1];
        for (let i = n-2; i >= 0; --i) suf[i] = Math.max(suf[i+1], d[i]);
        let ans = 0;
        for (let i = 0; i < n-1; ++i) ans = Math.max(ans, pre[i] * suf[i+1]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of the string. For each center, we expand to find the largest odd-length palindrome.
  • 🧺 Space complexity: O(n), for the prefix and suffix arrays.