Maximum Product of The Length of Two Palindromic Substrings in Java
Given a string s and the 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 1
Input: s = “ab”
Output: 1
Explanation: Substrings “a” and “b” are palindromes and product = 1*1=1.
Example 2
Input: s = “zaaaxbbby”
Output: 9
Explanation: Substrings “aaa” and “bbb” are palindromes with odd length and product = 3 * 3 = 9.
Example 3
Input: s = “ababbb”
Output: 9
Explanation: Substrings “aba” and “bbb” are palindromes with odd length. product = 3 * 3 = 9.
Approach 1: Using Dynamic Programming
The program utilizes Dynamic Programming to efficiently compute the length of the longest palindromic substring ending at each index. Then, it iterates through all pairs of indices and calculates the product of their respective palindrome lengths, eventually returning the maximum product found.
Algorithm
Step 1: Define a function isPalindrome to check if a given substring is a palindrome.
Step 2: Initialize an array dp to store the length of the longest palindromic substring ending at each index.
Step 3: Iterate over the string and for each index i, compute the length of the longest palindrome ending at i by checking all substrings ending at i.
Step 4: Calculate the maximum product of lengths of two palindromic substrings by iterating through all pairs of indices and multiplying their respective palindrome lengths.
Filename: MaximumProductOfPalindromicSubstringsUsingDP.java
public class MaximumProductOfPalindromicSubstringsUsingDP {
// Function to check if a substring is palindrome
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end))
return false;
start++;
end--;
}
return true;
}
public int maxProduct(String s) {
int n = s.length();
int[] dp = new int[n]; // dp[i] stores the length of the longest palindromic substring ending at index i
// Calculate the length of the longest palindromic substring ending at each index
for (int i = 0; i < n; i++) {
int maxLen = 0;
for (int j = 0; j <= i; j++) {
if (isPalindrome(s, j, i)) {
maxLen = Math.max(maxLen, i - j + 1);
}
}
dp[i] = maxLen;
}
int maxProduct = 0;
// Calculate the maximum product of lengths of two palindromic substrings
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
maxProduct = Math.max(maxProduct, dp[i] * dp[j]);
}
}
return maxProduct;
}
public static void main(String[] args) {
MaximumProductOfPalindromicSubstringsUsingDP solution = new MaximumProductOfPalindromicSubstringsUsingDP();
String s = "ababbb";
System.out.println("Maximum product of the lengths of two palindromic substrings: " + solution.maxProduct(s));
}
}
Output
Maximum product of the lengths of two palindromic substrings: 9
Time Complexity: The time complexity of an algorithm is O(n^2), where n is the length of the input string. This is because of the maximum product of lengths of two palindromic substrings by iterating through all pairs of indices.
Space Complexity: The space complexity of an algorithm is O(n), where n is the length of the input string. This is because the additional array dp of length n stores the lengths of the longest palindromic substrings ending at each index.
Approach 2: Using Brute Force
The program utilizes a brute force approach to compute all possible substrings of the given string and checks each pair of substrings to determine if they are palindromes. It then calculates the product of the lengths of those palindromic substrings and updates the maximum product found.
Algorithm
Step 1: Define a function isPalindrome to check if a given substring is a palindrome.
Step 2: Initialize a variable maxProduct to store the maximum product of palindrome lengths found.
Step 3: Iterate over all pairs of indices (i, j) where i ranges from 0 to n - 2 and j ranges from i + 1 to n - 1.x
Step 4: For each pair (i, j), check if the substring from index i to index j is a palindrome using the isPalindrome function.
Step 5: If it is a palindrome, calculate its length, square it, and update maxProduct if necessary.
Step 6: Finally, return the maximum product of palindrome lengths found.
Filename: MaximumProductOfPalindromicSubstringsBruteForce.java
public class MaximumProductOfPalindromicSubstringsBruteForce {
// Function to check if a substring is palindrome
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end))
return false;
start++;
end--;
}
return true;
}
public int maxProduct(String s) {
int n = s.length();
int maxProduct = 0;
// Calculate the maximum product of lengths of two palindromic substrings
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (isPalindrome(s, i, j)) {
maxProduct = Math.max(maxProduct, (j - i + 1) * (j - i + 1));
}
}
}
return maxProduct;
}
public static void main(String[] args) {
MaximumProductOfPalindromicSubstringsBruteForce solution = new MaximumProductOfPalindromicSubstringsBruteForce();
String s = "ababbb";
System.out.println("Maximum product of the lengths of two palindromic substrings: " + solution.maxProduct(s));
}
}
Output
Maximum product of the lengths of two palindromic substrings: 9
Time Complexity: The time complexity of a brute force approach is O(n^3), where n is the length of the input string. This is because it computes all possible substrings and for each substring, the function takes O(n) time to determine if it's a palindrome.
Space Complexity: The space complexity of an algorithm is O(1). This is because the algorithm only uses a constant amount of extra space for variables and function calls, regardless of the input size.
Approach 3: Using Manacher’s algorithm
Manacher's algorithm is an efficient technique for finding all palindromic substrings in linear time.
Algorithm
Step 1: We preprocess the input string by adding special characters between each character and at the beginning and end to handle both even and odd-length palindromes efficiently.
Step 2: We maintain an array of palindromicLengths to store the lengths of the palindromes centered at each position.
Step 3: Initialize two variables center and right, which represent the center and the right boundary of the rightmost palindrome found so far.
Step 4: Iterate through the processed string and use the mirror property to expand around the current center efficiently.
Step 5: While expanding, we update the palindromicLengths array and adjust the center and right boundaries accordingly.
Step 6: We calculate the maximum product of lengths of two palindromic substrings by considering only odd-length.
Filename: MaximumProductOfPalindromicSubstringsUsingManacher.java
public class MaximumProductOfPalindromicSubstringsUsingManacher {
public int maxProduct(String s) {
int n = s.length();
char[] paddedString = new char[2 * n + 1];
for (int i = 0; i < n; i++) {
paddedString[2 * i] = '#';
paddedString[2 * i + 1] = s.charAt(i);
}
paddedString[2 * n] = '#';
int[] palindromicLengths = new int[2 * n + 1];
int center = 0, right = 0;
int maxProduct = 0;
for (int i = 1; i < 2 * n; i++) {
int mirror = 2 * center - i;
if (i < right) {
palindromicLengths[i] = Math.min(right - i, palindromicLengths[mirror]);
}
// Expand around current center
while (i - 1 - palindromicLengths[i] >= 0 && i + 1 + palindromicLengths[i] < 2 * n + 1 &&
paddedString[i - 1 - palindromicLengths[i]] == paddedString[i + 1 + palindromicLengths[i]]) {
palindromicLengths[i]++;
}
// Update center and right boundary
if (i + palindromicLengths[i] > right) {
center = i;
right = i + palindromicLengths[i];
}
// Calculate the maximum product of lengths of two palindromic substrings
if (i % 2 == 1) { // If current position is in the original string
maxProduct = Math.max(maxProduct, palindromicLengths[i] * palindromicLengths[i]);
}
}
return maxProduct;
}
public static void main(String[] args) {
MaximumProductOfPalindromicSubstringsUsingManacher solution = new MaximumProductOfPalindromicSubstringsUsingManacher();
String s = "ababbb";
System.out.println("Maximum product of the lengths of two palindromic substrings: " + solution.maxProduct(s));
}
}
Output
Maximum product of the lengths of two palindromic substrings: 9
Time Complexity: The time complexity of a Manacher’s algorithm in linear time is O(n), where n is the length of the input string. The linear time complexity arises from the efficient linear expansion of palindromes using the mirror property.
Space Complexity: The space complexity is O(n) due to the additional array of length 2n + 1 to store the lengths of palindromic substrings. This is because a constant amount of extra space is used for variables and function calls.