Strings - Maximum Product of The Length of Two Palindromic Subsequences

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.

Return the maximum possible product of the lengths of the two palindromic subsequences.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.

Input: s = "codingisfun"
Output: 9
Explanation: An optimal solution is to choose "igi" for the 1^st subsequence and "nfn" for the 2^nd subsequence.
The product of their lengths is: 3 * 3 = 9.
Example 1

Input: s = "bb"
Output: 1
Explanation: An optimal solution is to choose "b" (the first character) for the 1st subsequence and "b" (the second character) for the 2nd subsequence.
The product of their lengths is: 1 * 1 = 1.

Input: s = "accbcaxxcxx"
Output: 25
Explanation: An optimal solution is to choose "b" (the first character) for the 1st subsequence and "b" (the second character) for the 2nd subsequence.
The product of their lengths is: 1 * 1 = 1.

Constraints:

2 <= s.length <= 12
s consists of lowercase English letters only

Solution 1 - Generate all possible subsequences recursively using DFS, then find max length product of disjoint subsequences
Solution 2 - Generate all possible subsequences using bit masking, then find max length product of disjoint subsequences

In this approach, we are going to generate pairs of all possible disjoint subsequences recursively and check if both are palindromes, if they are palindromes, then find product of maximum length palindromes among them.

Implementation steps:

In this implementation, we will use two variables s1 and s2 and initialize them with empty strings to start with "".
Then, we will generate pairs of disjoint subsequences by doing this:
- Add character at i^th position from input string to s1, without changing s2.
- Add character at i^th position from input string to s2, without changing s1.
- Without adding any characters, take s1 and s2 as is from previous inputs.
Then, call this procedure recursively until we used all characters from input string s.

For example, consider input string s = "codingisfun"
Initially s1 ="" and s2 = ""
Then, we take 1^st character from input string, which is c, now we will generate subsequence pair s1 = "c" and s2 ="" remains same. Next, add same character to s2 and s1 remains unchanged, s1 = "" and s2 ="c"

We will repeat this for all combinations of characters by recursively calling this procedure.
Base case for this recursive function is when we reach end of input string, we will check if s1 and s2 are palindromes then return their lengths product.
When we call above procedure, for three different inputs, we will get theree results.
1. s1 being appended with new characters, s2 remains same, call the result as left.
2. s2 being appended with new characters, s1 remains same, call the result as right.
3. s1 and s2 remains unchanged with disjoint pair of subsequences passed originally to recursive function, before adding characters to either s1 or s2, call the result as center.
Finally, take the maximum out of these 3 results.

public class MaxProductOfTwoDisjointPalindromes { /* Brute force approach using depth-first-search*/ static int maxProductUsingBruteForceApproach1_DFS(String s) { return dfs(s, 0, "", ""); } static int dfs(String s, int i, String s1, String s2) { if(i>= s.length()) { if(isPalindrome(s1) && isPalindrome(s2)) { return s1.length() * s2.length(); } return 0; } int left = dfs(s, i+1, s1+s.charAt(i), s2); int right = dfs(s, i+1, s1, s2+s.charAt(i)); int center = dfs(s, i+1, s1, s2); return Math.max(center, Math.max(left, right)); } static boolean isPalindrome(String input) { for(int i=0; i< input.length()/2; i++) { if(input.charAt(i) != input.charAt(input.length()-1 -i)) { return false; } } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O(n * 3ⁿ) time where n is the length of input string s Since we are generating all possible subsequences using by calling dfs function recursively with 3 different inputs and this takes O (3ⁿ), and then checking whether the strings s1 and s2 are palindromes, that takes O (n)
Space complexity: O(3ⁿ), since we are making recursive calls, this space is being used by the stack memory.

This approach is also going to be a brute-force solution, but we will generate all possible subsequences using bit masking, meaning that when generating all possible subsequences, we will represent each character of input string s with either 1 or 0.

Let's understand with an example, say the given input string is s = "codingisfun", since there are 11 characters in input string, there are 2ⁿ-1 possible subsequences. So, using bit masking we can represent these using bit masking, the characters which we are using in the subsequence, we will put 1 in the same position as in input string position, to represent that we are using that particular character in subsequence. Below are few for example:

c => 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

code => 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0

o => 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0

ode => 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0

codeingisfun => 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Implementation steps:

We will generate all possible subsequences using a for loop, going from i = 1 to 2ⁿ-1, then for each of the number in this loop, we need to find out which characters that we are going to consider. For example if i =1 we will need to get only the first character from input string s, so we will use another loop from j = 0...., s.length(), then perform bitwise operation i & (1 < < j) > 0 to know which character need to be considered for i^th subsequence, let's break it down why we are using this bitwise operation. (If you need to refresh BitWise operations, take a look at Bitwise Operators)
- Left shift bitwise operator, (1 << j) creates a mask with the j^th bit set to 1 (where j ranges from 0 to N-1). For example, it generates masks by moving 1 bit to left side... 00000000001, 00000000010, so on until 10000000000.
- i & (1 << j) performs a bitwise AND operation between the number i and the mask (1 << j), and if the result is non-zero, it means it means that the j^th bit in i is set to 1, indicating that the character at position j should be included in the current subsequence being generated.
While generating subsequences, we will also check if the subsequence is a palindrome, if it is a palindrome then cache its length into an array (call it cache) with position as i.
Now, finally loop through cache in a nested loop, since we need to find out disjoint subsequences, to find such unique subsequences, we can use logical AND (&) on the indices of nested loops, and check if the result is 0 i & j == 0, this means that they have bit 1 in different positions, so they are disjoint subsequences, so compute the product of their lengths and keep track of maximum value.

public class MaxProductOfTwoDisjointPalindromes { /* Brute force approach using Bit masking*/ static int maxProductUsingBruteForceApproach2_BitMasking(String s) { int mask = 1 <<s.length(); // all possible subsequences 2 power n int[] cache = new int[mask]; for (int i=1; i<mask ;i++) { // we are starting with i = 1 because bit-masking with all zeros doesn't represent // any subsequence String subSequence = ""; for(int j=0; j<s.length(); j++) { if( (i & (1 << j)) > 0) { // whether to include current character from j with mask being i subSequence += s.charAt(j); } } // now check subsequence reads same from both directions, for e.g. stats if(isPalindrome(subSequence)) { cache[i] = subSequence.length(); } } // since we have stored all possible palindromes and their length stored in dp array // now, find disjoint ones and max product among them int maxProduct = 0; for(int i=0; i<cache.length; i++) { for(int j=0; j<cache.length; j++) { if((i &j) ==0) { // disjoint indexes maxProduct = Math.max(maxProduct, cache[i] * cache[j]); } } } return maxProduct; } static boolean isPalindrome(String input) { for(int i=0; i< input.length()/2; i++) { if(input.charAt(i) != input.charAt(input.length()-1 -i)) { return false; } } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O((2ⁿ * n) + n²) time where n is the length of input string s Since we are generating all possible subsequences using a for loop 2ⁿ -1 times, and checking each subsequence is a palindrome or not, this takes O(2ⁿ * n), then checking disjoint subsequences pair in nested loop, this takes O(n²).
Space complexity: O(n), since we are caching lengths of subsequences.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis:

Implementation steps:

Complexity Analysis: