Problem Explanation

You are given a string s and your task is to find two non-intersecting palindromic substrings of odd length such that the product of their lengths is maximized. Both the substrings should be palindromes and have odd lengths.

A palindrome is a string that is the same forward and backward. A substring is a contiguous sequence of characters in a string.

Example

Let's walk through an example to understand the problem better.

Input: s = “ababbb” Output: 9

In this example, we have two substrings, "aba" and "bbb", which are palindromes with odd lengths. We can calculate the product as follows: 3 * 3 = 9, and thus, the output is 9.

Approach

The approach we will use for this problem is the Manacher's Algorithm. Here are the steps we will follow:

1. For each position in the string s, find the length of the longest palindrome that has the center at that position.
2. Find two non-overlapping longest palindromes.
3. Return the product of the lengths of the two longest non-overlapping palindromes.

Manacher's Algorithm

Manacher's Algorithm is an efficient method to find the longest palindromic substring in linear time complexity. It works by calculating the lengths of all palindromic substrings for each position in the given string, hence finding the longest palindrome substring.

Algorithm Steps

1. Implement the Manacher's Algorithm and store the length of the longest palindrome centered at each position in an array.
2. Find the left to right and right to left longest palindromes using the array derived in step 1.
3. Iterate through the array, finding two non-overlapping longest palindromes.
4. Return the product of the lengths of the two non-overlapping longest palindromes.

Now, let's implement the solution in different languages.

C++ Solution

1
2cpp
3class Solution {
4    public:
5        long long maxProduct(string s) {
6            const int n = s.length();
7            long long ans = 1;
8            // l[i] := max length of palindromes in s[0..i)
9            vector<int> l = manacher(s, n);
10            // r[i] := max length of palindromes in s[i..n)
11            vector<int> r = manacher(string(rbegin(s), rend(s)), n);
12            reverse(begin(r), end(r));
13
14            for (int i = 0; i + 1 < n; ++i)
15                ans = max(ans, (long long)l[i] * r[i + 1]);
16
17            return ans;
18        }
19
20    private:
21        vector<int> manacher(const string& s, int n) {
22            vector<int> maxExtends(n);
23            vector<int> l2r(n, 1);
24            int center = 0;
25
26            for (int i = 0; i < n; ++i) {
27                const int r = center + maxExtends[center] - 1;
28                const int mirrorIndex = center - (i - center);
29                int extend = i > r ? 1 : min(maxExtends[mirrorIndex], r - i + 1);
30                while (i - extend >= 0 && i + extend < n &&
31                        s[i - extend] == s[i + extend]) {
32                    l2r[i + extend] = 2 * extend + 1;
33                    ++extend;
34                }
35                maxExtends[i] = extend;
36                if (i + maxExtends[i] >= r)
37                    center = i;
38            }
39
40            for (int i = 1; i < n; ++i)
41                l2r[i] = max(l2r[i], l2r[i - 1]);
42
43            return l2r;
44        }
45};

We will now implement the solution in other languages.## Python Solution

1
2python
3class Solution:
4    def maxProduct(self, s: str) -> int:
5        n = len(s)
6        ans = 1
7        l = self.manacher(s, n)
8        r = self.manacher(s[::-1], n)
9        r.reverse()
10
11        for i in range(n - 1):
12            ans = max(ans, l[i] * r[i + 1])
13
14        return ans
15
16    def manacher(self, s: str, n: int) -> list:
17        maxExtends = [0] * n
18        l2r = [1] * n
19        center = 0
20
21        for i in range(n):
22            r = center + maxExtends[center] - 1
23            mirrorIndex = center - (i - center)
24            extend = 1 if i > r else min(maxExtends[mirrorIndex], r - i + 1)
25            while i - extend >= 0 and i + extend < n and s[i - extend] == s[i + extend]:
26                l2r[i + extend] = 2 * extend + 1
27                extend += 1
28            maxExtends[i] = extend
29            if i + maxExtends[i] >= r:
30                center = i
31
32        for i in range(1, n):
33            l2r[i] = max(l2r[i], l2r[i - 1])
34
35        return l2r

JavaScript Solution

1
2javascript
3class Solution {
4    maxProduct(s) {
5        const n = s.length;
6        let ans = 1;
7        const l = this.manacher(s, n);
8        const r = this.manacher(s.split('').reverse().join(''), n);
9        r.reverse();
10
11        for (let i = 0; i + 1 < n; ++i)
12            ans = Math.max(ans, l[i] * r[i + 1]);
13
14        return ans;
15    }
16
17    manacher(s, n) {
18        const maxExtends = new Array(n).fill(0);
19        const l2r = new Array(n).fill(1);
20        let center = 0;
21
22        for (let i = 0; i < n; ++i) {
23            const r = center + maxExtends[center] - 1;
24            const mirrorIndex = center - (i - center);
25            let extend = i > r ? 1 : Math.min(maxExtends[mirrorIndex], r - i + 1);
26            while (i - extend >= 0 && i + extend < n &&
27                s[i - extend] === s[i + extend]) {
28                l2r[i + extend] = 2 * extend + 1;
29                ++extend;
30            }
31            maxExtends[i] = extend;
32            if (i + maxExtends[i] >= r)
33                center = i;
34        }
35
36        for (let i = 1; i < n; ++i)
37            l2r[i] = Math.max(l2r[i], l2r[i - 1]);
38
39        return l2r;
40    }
41}

Java Solution

1
2java
3class Solution {
4    public int maxProduct(String s) {
5        int n = s.length();
6        int ans = 1;
7        int[] l = manacher(s, n);
8        int[] r = manacher(new StringBuilder(s).reverse().toString(), n);
9        int[] reverseR = new int[n];
10        for (int i = 0; i < n; ++i) {
11            reverseR[i] = r[n - i - 1];
12        }
13
14        for (int i = 0; i + 1 < n; ++i) {
15            ans = Math.max(ans, l[i] * reverseR[i + 1]);
16        }
17
18        return ans;
19    }
20
21    private int[] manacher(String s, int n) {
22        int[] maxExtends = new int[n];
23        int[] l2r = new int[n];
24        int center = 0;
25
26        for (int i = 0; i < n; ++i) {
27            int r = center + maxExtends[center] - 1;
28            int mirrorIndex = center - (i - center);
29            int extend = i > r ? 1 : Math.min(maxExtends[mirrorIndex], r - i + 1);
30            while (i - extend >= 0 && i + extend < n &&
31                    s.charAt(i - extend) == s.charAt(i + extend)) {
32                l2r[i + extend] = 2 * extend + 1;
33                ++extend;
34            }
35            maxExtends[i] = extend;
36            if (i + maxExtends[i] >= r) {
37                center = i;
38            }
39        }
40
41        for (int i = 1; i < n; ++i) {
42            l2r[i] = Math.max(l2r[i], l2r[i - 1]);
43        }
44
45        return l2r;
46    }
47}

These solutions in C++, Python, JavaScript, and Java implement the Manacher's Algorithm to find the two non-intersecting palindromic substrings of odd length with the maximum product of their lengths in a given string s.

Solution Implementation