## Similar Problems

Similar Problems not available

# Maximum Product Of The Length Of Two Palindromic Substrings - Leetcode Solution

## Companies:

LeetCode: Maximum Product Of The Length Of Two Palindromic Substrings Leetcode Solution

Difficulty: Hard

Topics: string

Problem Statement:

Given a string s, find two palindromic substrings that are non-overlapping and the product of their lengths is maximum. Return the maximum product.

Constraints:

1 <= s.length <= 10^5 s consists of lowercase English letters only.

Solution:

In this problem, we are looking for two longest palindromic substrings that are non-overlapping.

The first step is to find all the palindromic substrings in the given string. We can use dynamic programming to achieve this. The idea is to maintain a 2D boolean array pal[i][j] which will be true if the substring s[i...j] is a palindrome.

Next, we will find two non-overlapping palindromic substrings and calculate their product of length. We can do this by iterating through all the palindromic substrings and finding two that are non-overlapping and have the maximum product.

Let's discuss the implementation.

- Step 1: Finding all the palindromic substrings We can use dynamic programming to maintain a 2D boolean array pal[i][j]. We can apply the following recurrence relation to fill up the array: pal[i][j] = s[i] == s[j] and pal[i + 1][j - 1].

We start with substrings of length 1 and 2. For every substring of length i, we calculate the boolean values for all substrings of length i+1.

The time complexity of this step is O(n^2) and the space complexity is O(n^2).

- Step 2: Finding two non-overlapping palindromic substrings with maximum product We can use two nested loops to iterate through all the palindromic substrings and find two that are non-overlapping and have the maximum product of length.

The time complexity of this step is O(n^3) and the space complexity is O(1).

Overall, the time complexity of the solution is O(n^3) and the space complexity is O(n^2) which can be improved but is optimal for palindromic substring problems.

Code:

```
class Solution {
public:
int maxProduct(string s) {
int n = s.size();
vector<vector<bool>> pal(n, vector<bool>(n, false));
// Step 1: Finding all the palindromic substrings
for(int i=0; i<n; i++){
pal[i][i] = true;
}
for(int i=0; i<n-1; i++){
if(s[i] == s[i+1]){
pal[i][i+1] = true;
}
}
for(int i=n-3; i>=0; i--){
for(int j=i+2; j<n; j++){
if(s[i] == s[j] && pal[i+1][j-1]){
pal[i][j] = true;
}
}
}
// Step 2: Finding two non-overlapping palindromic substrings with maximum product
int ans = 0;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
if(pal[i][j]){
for(int k=j+1; k<n; k++){
for(int l=k+1; l<n; l++){
if(pal[k][l]){
if((l-k+1)*(j-i+1) > ans && check(i, j, k, l)){
ans = (l-k+1)*(j-i+1);
}
}
}
}
}
}
}
return ans;
}
bool check(int i, int j, int k, int l){
if(i >= k && j <= l){
return false;
}
if(k >= i && l <= j){
return false;
}
return true;
}
};
```

In this code, the function "check" checks if two palindromic substrings overlap. This is necessary because we only want to consider non-overlapping palindromic substrings.

Sample Input and Output:

Input: s = "ababa" Output: 9 Explanation: The two palindromic substrings are "aba" and "aba".

Input: s = "abb" Output: 1 Explanation: The only palindromic substring is "bb".

## Maximum Product Of The Length Of Two Palindromic Substrings Solution Code

`1`