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