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

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

1