Given a string S and a positive integer K, The task is to maximize the product of the length of non-overlapping palindromic substrings each of length at least K from the string S.
Examples:
Input: S = “abaccdbbd”, K = 3
Output: 12
Explanation: Select the substrings underlined in s = “abaccdbbd“, which is of length 3 and 4. The product of these results is 12, which is the most optimal answer.Input: S = “adbcda”, K = 2
Output: 0
Explanation: There is no palindrome of length at least 2.
An approach using Dynamic programming:
Precalculate all the palindromic substrings. Every index has two options either our valid palindrome will start from here which we include in our optimal result or we exclude the current index. Finally, maximize the result obtained it.
Follow the steps below to implement the above idea:
- Declare a 2D dp[] array to store if the substring from any i to any j is a palindrome or not.
- Initialize a dp2 array with -1, where dp2[i] will store the maximum result possible till index i.
- Precalculate to find all the substrings which are palindrome.
- Call a recursive function [say maxProduct()] and do the following:
- If current index i equal n (length of the given string), return 1.
- Check if the calculation for ith index is already done in the dp2[] array, if done then return the stored value from it.
- Find the valid substring which is a palindrome string starting from the current index.
- Recursively call for another palindromic substring after the ending of the first valid substring.
- Recursively call for the condition when ith character is not considered to be the starting position of a valid palindromic substring.
- Store calculation for the ith index into the dp2[] array
- Return the maximum value returned from the recursive function as the required result.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;int maxProduct(int i, string& s, int k, vector<vector<bool> >& dp, vector<int>& dp2){ // Base condition if (i == s.size()) return 1; // Check calculation in dp2 if (dp2[i] != -1) return dp2[i]; int result = 0; // Find the substring which // is palindrome for (int j = i; j < s.size(); j++) { // Valid palindromic substring of // length at least k if (dp[i][j] && j - i + 1 >= k) { // Recursive call for other // palindromic substring after // the ending of first valid // substring. result = max(result, (j - i + 1) * maxProduct(j + 1, s, k, dp, dp2)); } } // If we don't include ith character // to be the starting position of a // valid palindromic substring result = max(result, maxProduct(i + 1, s, k, dp, dp2)); // Store calculation for ith index // into dp array return dp2[i] = result;}// Function to find the maximum productint maxPalindromes(string s, int k){ int n = s.size(); // Declare a 2D dp array to store // all the palindromic substring vector<vector<bool> > dp(n + 1, vector<bool>(n + 1, false)); // Initialise a dp2 array with -1, where // dp2[i] will store the maximum // result possible till index i vector<int> dp2(n + 1, -1); // Precalculation of finding all the // substring which is palindrome // Finding all one length // palindromic substring for (int i = 0; i < n; i++) { dp[i][i] = true; } // Finding all two length // palindromic substring for (int i = 0; i < n - 1; i++) { if (s[i] == s[i + 1]) { dp[i][i + 1] = true; } } // Finding all possible length // palindromic substring starting from // length 3 till length of given string. for (int len = 3; len < n; len++) { int i = 0, j = len - 1; while (j < n) { if (s[i] == s[j]) { if (dp[i + 1][j - 1]) dp[i][j] = true; } i++; j++; } } // Function call to maxProduct. int ans = maxProduct(0, s, k, dp, dp2); // Because for k > 1 no substring of // length 1 is possible that is considered // as the default case in the function if (ans == 1 and k > 1) return 0; return ans;}// Drivers codeint main(){ // First test case string S = "abaccdbbd"; int K = 3; cout << maxPalindromes(S, K) << endl; // Second test case S = "adbcda"; K = 2; cout << maxPalindromes(S, K) << endl; // Third test case S = "ab"; K = 1; cout << maxPalindromes(S, K) << endl; return 0;} |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class GFG { static int maxProduct(int i, String s, int k, boolean[][] dp, int[] dp2) { // Base condition if (i == s.length()) { return 1; } // Check calculation in dp2 if (dp2[i] != -1) { return dp2[i]; } int result = 0; // Find the substring which // is palindrome for (int j = i; j < s.length(); j++) { // Valid palindromic substring of // length at least k if (dp[i][j] && j - i + 1 >= k) { // Recursive call for other // palindromic substring after // the ending of first valid // substring. result = Math.max( result, (j - i + 1) * maxProduct(j + 1, s, k, dp, dp2)); } } // If we don't include ith character // to be the starting position of a // valid palindromic substring result = Math.max(result, maxProduct(i + 1, s, k, dp, dp2)); // Store calculation for ith index // into dp array return dp2[i] = result; } // Function to find the maximum product static int maxPalindromes(String s, int k) { int n = s.length(); // Declare a 2D dp array to store // all the palindromic substring boolean[][] dp = new boolean[n + 1][n + 1]; // Initialise a dp2 array with -1, where // dp2[i] will store the maximum // result possible till index i int[] dp2 = new int[n + 1]; Arrays.fill(dp2, -1); // Precalculation of finding all the // substring which is palindrome // Finding all one length // palindromic substring for (int i = 0; i < n; i++) { dp[i][i] = true; } // Finding all two length // palindromic substring for (int i = 0; i < n - 1; i++) { if (s.charAt(i) == s.charAt(i + 1)) { dp[i][i + 1] = true; } } // Finding all possible length // palindromic substring starting from // length 3 till length of given string. for (int len = 3; len < n; len++) { int i = 0, j = len - 1; while (j < n) { if (s.charAt(i) == s.charAt(j)) { if (dp[i + 1][j - 1]) dp[i][j] = true; } i++; j++; } } // Function call to maxProduct. int ans = maxProduct(0, s, k, dp, dp2); // Because for k > 1 no substring of // length 1 is possible that is considered // as the default case in the function if (ans == 1 && k > 1) return 0; return ans; } public static void main(String[] args) { // First test case String S = "abaccdbbd"; int K = 3; System.out.println(maxPalindromes(S, K)); // Second test case S = "adbcda"; K = 2; System.out.println(maxPalindromes(S, K)); // Third test case S = "ab"; K = 1; System.out.println(maxPalindromes(S, K)); }}// This code is contributed by lokesh |
Python3
# python3 code for the above approachdef maxProduct(i, s, k, dp, dp2): # Base condition if (i == len(s)): return 1 # Check calculation in dp2 if (dp2[i] != -1): return dp2[i] result = 0 # Find the substring which # is palindrome for j in range(i, len(s)): # Valid palindromic substring of # length at least k if (dp[i][j] and j - i + 1 >= k): # Recursive call for other # palindromic substring after # the ending of first valid # substring. result = max(result, (j - i + 1) * maxProduct(j + 1, s, k, dp, dp2)) # If we don't include ith character # to be the starting position of a # valid palindromic substring result = max(result, maxProduct(i + 1, s, k, dp, dp2)) # Store calculation for ith index # into dp array dp2[i] = result return dp2[i]# Function to find the maximum productdef maxPalindromes(s, k): n = len(s) # Declare a 2D dp array to store # all the palindromic substring dp = [[False for _ in range(n+1)] for _ in range(n+1)] # Initialise a dp2 array with -1, where # dp2[i] will store the maximum # result possible till index i dp2 = [-1 for _ in range(n + 1)] # Precalculation of finding all the # substring which is palindrome # Finding all one length # palindromic substring for i in range(0, n): dp[i][i] = True # Finding all two length # palindromic substring for i in range(0, n-1): if (s[i] == s[i + 1]): dp[i][i + 1] = True # Finding all possible length # palindromic substring starting from # length 3 till length of given string. for le in range(3, n): i = 0 j = le - 1 while (j < n): if (s[i] == s[j]): if (dp[i + 1][j - 1]): dp[i][j] = True i += 1 j += 1 # Function call to maxProduct. ans = maxProduct(0, s, k, dp, dp2) # Because for k > 1 no substring of # length 1 is possible that is considered # as the default case in the function if (ans == 1 and k > 1): return 0 return ans# Drivers codeif __name__ == "__main__": # First test case S = "abaccdbbd" K = 3 print(maxPalindromes(S, K)) # Second test case S = "adbcda" K = 2 print(maxPalindromes(S, K)) # Third test case S = "ab" K = 1 print(maxPalindromes(S, K)) # This code is contributed by rakeshsahni |
C#
// C# code for the above approachusing System;using System.Collections;public class GFG { // Function to find the maxProduct static int maxProduct(int i, String s, int k, bool[, ] dp, int[] dp2) { // Base condition if (i == s.Length) { return 1; } // Check calculation in dp2 if (dp2[i] != -1) { return dp2[i]; } int result = 0; // Find the substring which // is palindrome for (int j = i; j < s.Length; j++) { // Valid palindromic substring of // length at least k if (dp[i, j] && j - i + 1 >= k) { // Recursive call for other // palindromic substring after // the ending of first valid // substring. result = Math.Max( result, (j - i + 1) * maxProduct(j + 1, s, k, dp, dp2)); } } // If we don't include ith character // to be the starting position of a // valid palindromic substring result = Math.Max(result, maxProduct(i + 1, s, k, dp, dp2)); // Store calculation for ith index // into dp array return dp2[i] = result; } // Function to find the maximum product static int maxPalindromes(String s, int k) { int n = s.Length; // Declare a 2D dp array to store // all the palindromic substring bool[, ] dp = new bool[n + 1, n + 1]; // Initialise a dp2 array with -1, where // dp2[i] will store the maximum // result possible till index i int[] dp2 = new int[n + 1]; Array.Fill(dp2, -1); // Precalculation of finding all the // substring which is palindrome // Finding all one length // palindromic substring for (int i = 0; i < n; i++) { dp[i, i] = true; } // Finding all two length // palindromic substring for (int i = 0; i < n - 1; i++) { if (s[i] == s[i + 1]) { dp[i, i + 1] = true; } } // Finding all possible length // palindromic substring starting from // length 3 till length of given string. for (int len = 3; len < n; len++) { int i = 0, j = len - 1; while (j < n) { if (s[i] == s[j]) { if (dp[i + 1, j - 1]) dp[i, j] = true; } i++; j++; } } // Function call to maxProduct. int ans = maxProduct(0, s, k, dp, dp2); // Because for k > 1 no substring of // length 1 is possible that is considered // as the default case in the function if (ans == 1 && k > 1) return 0; return ans; } static public void Main() { // Code // First test case string S = "abaccdbbd"; int K = 3; Console.WriteLine(maxPalindromes(S, K)); // Second test case S = "adbcda"; K = 2; Console.WriteLine(maxPalindromes(S, K)); // Third test case S = "ab"; K = 1; Console.WriteLine(maxPalindromes(S, K)); }}// This code is contributed by lokesh |
Javascript
// JavaScript code for the above approachfunction maxProduct(i, s, k, dp, dp2){ // Base condition if (i === s.length) { return 1; } // Check calculation in dp2 if (dp2[i] !== -1) { return dp2[i]; } let result = 0; // Find the substring which is palindrome for (let j = i; j < s.length; j++) { // Valid palindromic substring of length at least k if (dp[i][j] && j - i + 1 >= k) { // Recursive call for other palindromic substring // after the ending of first valid substring. result = Math.max(result, (j - i + 1) * maxProduct(j + 1, s, k, dp, dp2)); } } // If we don't include ith character to be the // starting position of a valid palindromic substring result = Math.max(result, maxProduct(i + 1, s, k, dp, dp2)); // Store calculation for ith index into dp array return dp2[i] = result;}function maxPalindromes(s, k) { const n = s.length; // Declare a 2D dp array to store all the palindromic substring const dp = new Array(n + 1); for (let i = 0; i < n + 1; i++) { dp[i] = new Array(n + 1); } // Initialise a dp2 array with -1, where dp2[i] will // store the maximum result possible till index i const dp2 = new Array(n + 1).fill(-1); // Precalculation of finding all the substring // which is palindrome // Finding all one length palindromic substring for (let i = 0; i < n; i++) { dp[i][i] = true; } // Finding all two length palindromic substring for (let i = 0; i < n - 1; i++) { if (s[i] === s[i + 1]) { dp[i][i + 1] = true; } } // Finding all possible length palindromic substring // starting from length 3 till length of given string. for (let len = 3; len < n; len++) { let i = 0, j = len - 1; while (j < n) { if (s[i] === s[j]) { if (dp[i + 1][j - 1]) { dp[i][j] = true; } } i++; j++; } } // Function call to maxProduct. const ans = maxProduct(0, s, k, dp, dp2); // Because for k > 1 no substring of length 1 is possible // that is considered as the default case in the function if (ans === 1 && k > 1){ return 0; } return ans;}// First test caselet S = "abaccdbbd";let K = 3;console.log(maxPalindromes(S, K) + "<br>");// Second test caseS = "adbcda";K = 2;console.log(maxPalindromes(S, K) + "<br>");// Third test caseS = "ab";K = 1;console.log(maxPalindromes(S, K));// This code is contributed by lokeshmvs21. |
Output
12 0 1
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Below is the implementation of the above approach:
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum productint maxPalindromes(string s, int k){ int n = s.size(); vector<vector<bool> > dp(n, vector<bool>(n, false)); // Set values for substring of length 1 and 2 for (int i = 0; i < n; i++) { dp[i][i] = true; if (i < n - 1 && s[i] == s[i + 1]) { dp[i][i + 1] = true; } } // Fill values for substring of length 3 and more for (int len = 3; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (s[i] == s[j]) { dp[i][j] = dp[i + 1][j - 1]; } } } vector<int> dp2(n, -1); dp2[n - 1] = 1; // Fill in the dp2 array using tabulation for (int i = n - 2; i >= 0; i--) { dp2[i] = dp2[i + 1]; for (int j = i; j < n; j++) { if (dp[i][j] && (j - i + 1) >= k) { int temp = (j - i + 1); if (j + 1 < n) { temp *= dp2[j + 1]; } dp2[i] = max(dp2[i], temp); } } } if (dp2[0] == 1 && k > 1) { return 0; } // return final ansnwer return dp2[0];}// Drivers codeint main(){ // First test case string S = "abaccdbbd"; int K = 3; cout << maxPalindromes(S, K) << endl; // Second test case S = "adbcda"; K = 2; cout << maxPalindromes(S, K) << endl; // Third test case S = "ab"; K = 1; cout << maxPalindromes(S, K) << endl; return 0;} |
Java
import java.util.Arrays;class Main { // Function to find the maximum product static int maxPalindromes(String s, int k) { int n = s.length(); boolean[][] dp = new boolean[n][n]; // Set values for substring of length 1 and 2 for (int i = 0; i < n; i++) { dp[i][i] = true; if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) { dp[i][i + 1] = true; } } // Fill values for substring of length 3 and more for (int len = 3; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1]; } } } int[] dp2 = new int[n]; Arrays.fill(dp2, -1); dp2[n - 1] = 1; // Fill in the dp2 array using tabulation for (int i = n - 2; i >= 0; i--) { dp2[i] = dp2[i + 1]; for (int j = i; j < n; j++) { if (dp[i][j] && (j - i + 1) >= k) { int temp = (j - i + 1); if (j + 1 < n) { temp *= dp2[j + 1]; } dp2[i] = Math.max(dp2[i], temp); } } } if (dp2[0] == 1 && k > 1) { return 0; } // return final answer return dp2[0]; } // Drivers code public static void main(String[] args) { // First test case String S = "abaccdbbd"; int K = 3; System.out.println(maxPalindromes(S, K)); // Second test case S = "adbcda"; K = 2; System.out.println(maxPalindromes(S, K)); // Third test case S = "ab"; K = 1; System.out.println(maxPalindromes(S, K)); }} |
Python3
# Function to find the maximum productdef maxPalindromes(s, k): n = len(s) dp = [[False] * n for _ in range(n)] # Set values for substring of length 1 and 2 for i in range(n): dp[i][i] = True if i < n - 1 and s[i] == s[i + 1]: dp[i][i + 1] = True # Fill values for substring of length 3 and more for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] dp2 = [-1] * n dp2[n - 1] = 1 # Fill in the dp2 array using tabulation for i in range(n - 2, -1, -1): dp2[i] = dp2[i + 1] for j in range(i, n): if dp[i][j] and (j - i + 1) >= k: temp = (j - i + 1) if j + 1 < n: temp *= dp2[j + 1] dp2[i] = max(dp2[i], temp) if dp2[0] == 1 and k > 1: return 0 # return final ansnwer return dp2[0]# Test caseeS = "abaccdbbd"K = 3print(maxPalindromes(S, K))S = "adbcda"K = 2print(maxPalindromes(S, K))S = "ab"K = 1print(maxPalindromes(S, K)) |
C#
using System;using System.Collections.Generic;class GFG{ // Function to find the maximum product static int MaxPalindromes(string s, int k) { int n = s.Length; bool[,] dp = new bool[n, n]; // Set values for substring of length 1 and 2 for (int i = 0; i < n; i++) { dp[i, i] = true; if (i < n - 1 && s[i] == s[i + 1]) { dp[i, i + 1] = true; } } // Fill values for substring of length 3 and more for (int len = 3; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (s[i] == s[j]) { dp[i, j] = dp[i + 1, j - 1]; } } } int[] dp2 = new int[n]; dp2[n - 1] = 1; // Fill in the dp2 array using tabulation for (int i = n - 2; i >= 0; i--) { dp2[i] = dp2[i + 1]; for (int j = i; j < n; j++) { if (dp[i, j] && (j - i + 1) >= k) { int temp = (j - i + 1); if (j + 1 < n) { temp *= dp2[j + 1]; } dp2[i] = Math.Max(dp2[i], temp); } } } if (dp2[0] == 1 && k > 1) { return 0; } // Return final answer return dp2[0]; } static void Main(string[] args) { // Test case string S = "abaccdbbd"; int K = 3; Console.WriteLine(MaxPalindromes(S, K)); S = "adbcda"; K = 2; Console.WriteLine(MaxPalindromes(S, K)); S = "ab"; K = 1; Console.WriteLine(MaxPalindromes(S, K)); }} |
Javascript
// Function to find the maximum productconst maxPalindromes = (s, k) => { const n = s.length; const dp = Array.from({ length: n }, () => Array(n).fill(false)); // Set values for substring of length 1 and 2 for (let i = 0; i < n; i++) { dp[i][i] = true; if (i < n - 1 && s[i] === s[i + 1]) { dp[i][i + 1] = true; } } // Fill values for substring of length 3 and more for (let length = 3; length <= n; length++) { for (let i = 0; i < n - length + 1; i++) { const j = i + length - 1; if (s[i] === s[j]) { dp[i][j] = dp[i + 1][j - 1]; } } } const dp2 = Array(n).fill(-1); dp2[n - 1] = 1; // Fill in the dp2 array using tabulation for (let i = n - 2; i >= 0; i--) { dp2[i] = dp2[i + 1]; for (let j = i; j < n; j++) { if (dp[i][j] && (j - i + 1) >= k) { let temp = j - i + 1; if (j + 1 < n) { temp *= dp2[j + 1]; } dp2[i] = Math.max(dp2[i], temp); } } } if (dp2[0] === 1 && k > 1) { return 0; } // return final ansnwer return dp2[0];};// Test caselet S = "abaccdbbd";let K = 3;console.log(maxPalindromes(S, K));S = "adbcda";K = 2;console.log(maxPalindromes(S, K));S = "ab";K = 1;console.log(maxPalindromes(S, K)); |
Output
12 0 1
Time Complexity: O(N^2)
Auxiliary Space: O(N^2)
Related Articles:
- Introduction to Strings – Data Structures and Algorithms Tutorials
- Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
