1960. Maximum Product of the Length of Two Palindromic Substrings


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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Solution Implementation

Not Sure What to Study? Take the 2-min Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.
Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫