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

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> pal(n, vector(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”.

## Step by Step Implementation For Maximum Product Of The Length Of Two Palindromic Substrings

```public class Solution {
public int maxProduct(String[] words) {
if (words == null || words.length == 0)
return 0;
int len = words.length;

int[] value = new int[len];
for (int i = 0; i < len; i++) {
String tmp = words[i];
value[i] = 0;
for (int j = 0; j < tmp.length(); j++) {
value[i] |= 1 << (tmp.charAt(j) - 'a');
}
}
int maxProduct = 0;
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++) {
if ((value[i] & value[j]) == 0 && (words[i].length() * words[j].length() > maxProduct))
maxProduct = words[i].length() * words[j].length();
}
return maxProduct;
}
}```
```def longestPalindrome(s):
n = len(s)

# Create a table to store results of subproblems
table = [[0 for x in range(n)] for y in range(n)]

# Strings of length 1 are palindromes
maxLength = 1
i = 0
while (i < n):
table[i][i] = True
i = i + 1

# Check for lengths 2, 3, ... , n
start = 0
length = 2
while (length <= n):

# For substring of length 2
if (length == 2):
i = 0
while (i < n-1):
if (s[i] == s[i + 1]):
table[i][i + 1] = True
start = i
maxLength = length
i = i + 1
# For lengths greater than 2
else:
i = 0
while (i < n - length + 1):
j = i + length - 1
if (table[i + 1][j - 1] and s[i] == s[j]):
table[i][j] = True

if (length > maxLength):
start = i
maxLength = length
i = i + 1
length = length + 1
print("Longest palindrome substring is:")
print(s[start:start + maxLength])

return maxLength```
```/**
* @param {string} s
* @return {number}
*/
var maxProduct = function(s) {
let n = s.length,
max = 0;

// dp[i][j] is going to store the length of the
// longest palindromic subsequence in substring
// s[i..j]
let dp = Array(n);

// Fill dp[][] in bottom up manner
for (let i = n - 1; i >= 0; i--) {
dp[i] = Array(n);
dp[i][i] = 1; // length of a palindrome subsequence of length 1 is 1

for (let j = i + 1; j < n; j++) {
// If the first and last characters are same
if (s[i] == s[j]) {
dp[i][j] = 2 + dp[i + 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}

// update max if a palindromic subsequence
// of length 2 or more is found
if (dp[i][n - 1] > 1 && max < dp[i][n - 1] * dp[i][n - 1]) {
max = dp[i][n - 1] * dp[i][n - 1];
}
}

return max;
};```
```class Solution {
public:
int maxProduct(string s) {
int n = s.size();
int max_len = 1; // The result (length of LPS)

// Create a table to store results of subproblems
int L[n][n];

// Strings of length 1 are palindromes of length 1
for (int i = 0; i < n; i++)
L[i][i] = 1;

// Build the table. Note that the lower diagonal values of table are
// useless and not filled in the process. The values are filled in a
// manner similar to Matrix Chain Multiplication DP solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/). Since
// we need to find the length of longest palindromic substring, we find
// the corresponding length information from table made by LCS
// (https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/)
// process.
for (int cl=2; cl<=n; cl++)
{
for (int i=0; i max_len)
max_len = L[i][j];
}
}
return max_len;
}
};```
```public class Solution {
public int MaxProduct(string s) {
// maxProduct will keep track of the maximum product found so far
int maxProduct = 0;

// We will iterate through the string, keeping track of the start and end indices
// of the longest palindrome found so far
int start = 0;
int end = 0;

// We will also keep track of the longest palindrome found at each index
// This will allow us to avoid recalculating the length of a palindrome
// when we find one that contains a previously found palindrome
int[] longestPalindromeAtIndex = new int[s.Length];

for (int i = 0; i < s.Length; i++) {
// We check if there is a palindrome centered at index i - 1
// If there is, we can use the information stored in longestPalindromeAtIndex
// to avoid recalculating the length of the palindrome
if (i > 0 && longestPalindromeAtIndex[i - 1] > 0) {
// We check if the palindrome centered at index i - 1
// contains index i
if (i + longestPalindromeAtIndex[i - 1] / 2 == i) {
// If it does, we check if the characters at indices i - 1 and i + 1
// are the same
if (s[i - 1] == s[i + 1]) {
// If they are, we update longestPalindromeAtIndex[i]
longestPalindromeAtIndex[i] = longestPalindromeAtIndex[i - 1] + 2;

// We also update start and end if necessary
if (longestPalindromeAtIndex[i] > end - start) {
start = i - longestPalindromeAtIndex[i] / 2;
end = i + longestPalindromeAtIndex[i] / 2;
}
}
}
}
// If there is no palindrome centered at index i - 1
// or if the one centered at index i - 1 does not contain index i,
// we check if there is a palindrome centered at index i
else {
// We check if the characters at indices i - 1 and i + 1 are the same
if (s[i - 1] == s[i + 1]) {
// If they are, we update longestPalindromeAtIndex[i]
longestPalindromeAtIndex[i] = 3;

// We also update start and end if necessary
if (longestPalindromeAtIndex[i] > end - start) {
start = i - longestPalindromeAtIndex[i] / 2;
end = i + longestPalindromeAtIndex[i] / 2;
}
}
}

// We check if the palindrome centered at index i
// contains index i + 1
if (i + longestPalindromeAtIndex[i] / 2 == i + 1) {
// If it does, we check if the characters at indices i and i + 2
// are the same
if (s[i] == s[i + 2]) {
// If they are, we update longestPalindromeAtIndex[i + 1]
longestPalindromeAtIndex[i + 1] = longestPalindromeAtIndex[i] + 2;

// We also update start and end if necessary
if (longestPalindromeAtIndex[i + 1] > end - start) {
start = i + 1 - longestPalindromeAtIndex[i + 1] / 2;
end = i + 1 + longestPalindromeAtIndex[i + 1] / 2;
}
}
}

// We update maxProduct if necessary
if (longestPalindromeAtIndex[i] > maxProduct) {
maxProduct = longestPalindromeAtIndex[i];
}
}

return maxProduct;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://prepfortech.in/leetcode-solutions/maximum-product-of-the-length-of-two-palindromic-substrings/", "fetch_time": 1685755836000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-23/segments/1685224648911.0/warc/CC-MAIN-20230603000901-20230603030901-00414.warc.gz", "warc_record_offset": 520397891, "warc_record_length": 38639, "token_count": 2730, "char_count": 9047, "score": 4.25, "int_score": 4, "crawl": "CC-MAIN-2023-23", "snapshot_type": "longest", "language": "en", "language_score": 0.895068347454071, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00047-of-00064.parquet"}