2002. Maximum Product of the Length of Two Palindromic Subsequences
Problem Description
The problem is about finding two non-overlapping palindromic subsequences in a given string s
. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The goal is to maximize the product of the lengths of these two palindromic subsequences. A string is palindromic if it reads the same forward and backward. The main challenge is to ensure that the subsequences are disjoint, meaning they do not share characters at the same index positions.
Flowchart Walkthrough
To analyze LeetCode 2002, Maximum Product of the Length of Two Palindromic Subsequences, let’s use the algorithm flowchart. Here's how we deduce the suitable approach:
Is it a graph?
- No: The problem does involve direct graph-based interactions such as nodes or edges connectivity.
Need to solve for kth smallest/largest?
- No: The problem is focused on maximizing a product, not finding a specific ordered element.
Involves Linked Lists?
- No: This is not about managing or traversing linked lists.
Does the problem have small constraints?
- Yes: The problem's small constraints imply that we can consider exhaustive checks or generating subsets, as the input size is typically manageable.
Brute force / Backtracking?
- Yes: With small constraints, we can afford to explore all combinations of subsequences to ensure each is a palindrome and then calculate their lengths to maximize the product.
Conclusion: The flowchart suggests that the backtracking approach is most suitable for handling the exhaustive checks of palindrome subsequences while maintaining a manageable computational cost due to the small constraints of the problem.
Explore this flowchart for further clarifications or similar algorithmic decision-making processes: Algorithm Flowchart.
Intuition
The intuition behind the solution involves the following steps:
- Generate all possible subsequences of the string.
- Check which of these subsequences are palindromic.
- Attempt to pair each palindromic subsequence with another, ensuring they do not overlap (disjoint).
- Calculate the product of the lengths of each pair and keep track of the maximum product found.
The solution uses bitwise operations to efficiently represent and iterate over all subsequences. The bitmask representing each subsequence is used to check if two subsequences are disjoint by using XOR and AND operations. It also counts the number of set bits (1s
) in the bitmask using .bit_count()
to determine the length of the subsequence without actually constructing the subsequence string, which saves time and memory. Finally, it uses the precomputed palindromic status of each bitmask to quickly check if a subsequence is palindromic, avoiding repeated calculations.
Learn more about Dynamic Programming, Backtracking and Bitmask patterns.
Solution Approach
The solution provided leverages bit manipulation and dynamic programming to tackle the problem. The approach can be broken down into the following steps:
-
Precompute Palindromic Subsequences:
- We iterate over all possible subsequences represented by bitmasks where each bit corresponds to an index in the string
s
. A bit set to1
represents the inclusion of that character in the subsequence, while0
represents exclusion. - The variable
p
is an array where each index corresponds to a bitmask of a subsequence.p
is used to store whether the represented subsequence is palindromic or not. Initially, all values inp
are set toTrue
. - The first for loop goes through all possible bitmasks, using
k
. Nested while loops are then used to iterate from the outermost characters toward the center, checking if the characters are equal. If a pair of characters is not equal,p[k]
is set toFalse
and the loop breaks, indicating that this subsequence is not palindromic.
- We iterate over all possible subsequences represented by bitmasks where each bit corresponds to an index in the string
-
Find Maximized Product of Lengths:
- With all palindromic subsequences identified, we loop through them with the bitmask
i
. The bitmaskmx
is computed as the XOR ofi
with the bitmask representing all characters in the string (i.e.,(1 << n) - 1
). This essentially invertsi
, marking all indices not included ini
. - Then, we initialize
j
withmx
and enter a nested loop. Inside this loop, we only consider bitmasksj
that are palindromic (p[j] == True
). For each such bitmask, we use.bit_count()
to calculate the length of the palindromic subsequences corresponding to the bitmasksi
andj
(stored in variablesa
andb
, respectively). - The product of
a
andb
is calculated and checked against the current maximum productans
. If it is larger, it becomes the new maximum.
- With all palindromic subsequences identified, we loop through them with the bitmask
-
Iterate Over All Combinations:
- The critical optimization here is to iterate through all smaller bitmasks of
mx
that are still palindromic. This is done by decrementingj
at each step usingj = (j - 1) & mx
. By ANDing withmx
, we ensure we get smaller bitmasks that represent subsequences disjoint from subsequencei
.
- The critical optimization here is to iterate through all smaller bitmasks of
-
Return Result:
- After all combinations are checked, the maximum product calculated is stored in
ans
, which is returned as the result.
- After all combinations are checked, the maximum product calculated is stored in
The algorithm makes use of bit manipulation to efficiently enumerate subsequences and dynamically checks for palindromic properties to reduce redundant calculations. By exploiting bit counts and clever looping, it is able to quickly find the maximum product of the lengths of two disjoint palindromic subsequences.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example with the string s = "ababa"
. We want to find two non-overlapping palindromic subsequences that yield the maximum product of their lengths.
-
Precompute Palindromic Subsequences:
- First, we generate all possible subsequences using bit masks. For the string
s = "ababa"
which has a length of5
, we will have2^5 - 1 = 31
possible non-empty subsequences. - For simplicity, let's consider a few bitmasks and their corresponding subsequences:
00101
which represents the subsequence "aa" (palindromic)01010
which represents the subsequence "bbb" (not palindromic)10100
which represents the subsequence "aba" (palindromic)
- The array
p
would reflect if these subsequences are palindromic (True
orFalse
). For our example:p[5] = True
since the bitmask5 (00101)
is palindromic.p[10] = False
for10 (01010)
because it's not palindromic.p[20] = True
for20 (10100)
since it's palindromic.
- First, we generate all possible subsequences using bit masks. For the string
-
Find Maximized Product of Lengths:
- Now, we look for pairs of palindromic subsequences that do not overlap and calculate the product of their lengths.
- If we take the bitmask
20 (10100)
which corresponds to the subsequence "aba", we would then find the inverted bitmaskmx = 31 XOR 20 = 11 (01111)
representing 'b', 'ab', 'bb' or 'abb'. - Within the bitmask
11 (01111)
, we look for palindromic subsequences. - Let's say we find the bitmask
3 (00011)
which represents the subsequence "ab" and is also palindromic. - We check the lengths using
.bit_count()
: the length of20 (10100)
is3
and the length of3 (00011)
is2
. The product is3 * 2 = 6
.
-
Iterate Over All Combinations:
- We keep decrementing
j
usingj = (j - 1) & mx
to find all smaller, non-overlapping palindromic subsequences. - For instance, if
j
was initially11 (01111)
, the nextj
would be7 (00111)
, representing the subsequence "aab", which is not palindromic.
- We keep decrementing
-
Return Result:
- After examining all possible palindrome subsequence combinations, we determine the ones that give us the maximum product. In this example, the maximum product is
6
, given by the subsequences "aba" (length3
) and "ab" (length2
).
- After examining all possible palindrome subsequence combinations, we determine the ones that give us the maximum product. In this example, the maximum product is
This walkthrough provides a conceptual understanding of how the solution uses bit masks and dynamic programming to efficiently find the maximum product of lengths of two non-overlapping palindromic subsequences.
Solution Implementation
1class Solution:
2 def maxProduct(self, s: str) -> int:
3 # Length of the string
4 n = len(s)
5
6 # is_palindrome will denote if the binary representation of a number corresponds to a palindromic substring
7 is_palindrome = [True] * (1 << n)
8
9 # Precompute all palindromic substrings using bit representation
10 for bitmask in range(1, 1 << n):
11 left, right = 0, n - 1
12 while left < right:
13 # Find the next '1' bit from the left
14 while left < right and (bitmask >> left & 1) == 0:
15 left += 1
16 # Find the next '1' bit from the right
17 while left < right and (bitmask >> right & 1) == 0:
18 right -= 1
19 # If the corresponding characters do not match, this is not a palindrome
20 if left < right and s[left] != s[right]:
21 is_palindrome[bitmask] = False
22 break
23 left += 1
24 right -= 1
25
26 # Initialize the result for maximum product of the lengths
27 max_product = 0
28
29 # Iterate over all possible bitmasks
30 for i in range(1, 1 << n):
31 # Proceed only if the bitmask represents a palindrome
32 if is_palindrome[i]:
33 # Inverse bitmask: set bits become unset and vice versa
34 inverse_mask = ((1 << n) - 1) ^ i
35
36 # Iterate over all submasks of the inverse bitmask
37 j = inverse_mask
38 len_a = i.bit_count() # Count of set bits, giving the length of palindrome A
39 while j:
40 # If j represents a palindrome, calculate the product of the lengths
41 if is_palindrome[j]:
42 len_b = j.bit_count() # Length of palindrome B
43 max_product = max(max_product, len_a * len_b)
44 # Move to the next submask
45 j = (j - 1) & inverse_mask
46
47 return max_product
48
1import java.util.Arrays;
2
3class Solution {
4 public int maxProduct(String s) {
5 // Get the length of the string
6 int stringLength = s.length();
7 // Initialize a boolean array for palindrome checks with size as all possible subsets
8 boolean[] isPalindrome = new boolean[1 << stringLength];
9 // Default all entries to true
10 Arrays.fill(isPalindrome, true);
11
12 // Check each subset to see if it forms a palindrome
13 for (int subset = 1; subset < 1 << stringLength; ++subset) {
14 for (int left = 0, right = stringLength - 1; left < stringLength; ++left, --right) {
15 // Find the next index 'left' where subset has a bit set
16 while (left < right && (subset >> left & 1) == 0) {
17 ++left;
18 }
19 // Find the next index 'right' where subset has a bit set
20 while (left < right && (subset >> right & 1) == 0) {
21 --right;
22 }
23 // If the characters at 'left' and 'right' don't match, it's not a palindrome
24 if (left < right && s.charAt(left) != s.charAt(right)) {
25 isPalindrome[subset] = false;
26 break;
27 }
28 }
29 }
30
31 int maximumProduct = 0; // Initialize the maximum product of palindrome lengths
32
33 // Calculate the product of lengths for all pairs of palindromic subsets
34 for (int i = 1; i < 1 << stringLength; ++i) {
35 if (isPalindrome[i]) { // If the subset at index i forms a palindrome
36 int countA = Integer.bitCount(i); // Count the number of set bits
37
38 // Calculate the complement of subset i
39 int complement = ((1 << stringLength) - 1) ^ i;
40
41 // Iterate through all subsets of complement
42 for (int j = complement; j > 0; j = (j - 1) & complement) {
43 if (isPalindrome[j]) { // If the subset at index j forms a palindrome
44 int countB = Integer.bitCount(j); // Count the number of set bits
45 // Update the maximum product if the current pair product is larger
46 maximumProduct = Math.max(maximumProduct, countA * countB);
47 }
48 }
49 }
50 }
51
52 return maximumProduct; // Return the maximum product found
53 }
54}
55
1class Solution {
2public:
3 // Function to compute the maximum product of the lengths of two non-overlapping palindromic subsequences
4 int maxProduct(string s) {
5 int n = s.size(); // Get the size of the input string
6 vector<bool> isPalindrome(1 << n, true); // Initialize a vector to track if a subsequence represented by bitmask is a palindrome
7
8 // Check each subsequence represented by a bitmask to see if it is a palindrome
9 for (int mask = 1; mask < (1 << n); ++mask) {
10 for (int left = 0, right = n - 1; left < right; ++left, --right) {
11 // Advance the left index until it points to a character included in the subsequence
12 while (left < right && !(mask >> left & 1)) {
13 ++left;
14 }
15 // Move the right index back until it points to a character included in the subsequence
16 while (left < right && !(mask >> right & 1)) {
17 --right;
18 }
19 // If the characters at the current left and right indices do not match, this is not a palindrome
20 if (left < right && s[left] != s[right]) {
21 isPalindrome[mask] = false;
22 break;
23 }
24 }
25 }
26
27 int maxProduct = 0; // Initialize the maximum product to 0
28
29 // Iterate over all bitmasks to find the maximum product of palindromic subsequence pairs
30 for (int i = 1; i < (1 << n); ++i) {
31 if (isPalindrome[i]) { // Only consider the bitmask if it represents a palindrome
32 int lengthA = __builtin_popcount(i); // Compute the length of palindrome A
33 int complementMask = ((1 << n) - 1) ^ i; // Generate a bitmask for the complementary subsequence
34
35 // Find the other palindromic subsequence with the maximum length that can pair with the current one
36 for (int j = complementMask; j; j = (j - 1) & complementMask) {
37 if (isPalindrome[j]) {
38 int lengthB = __builtin_popcount(j); // Compute the length of palindrome B
39 maxProduct = max(maxProduct, lengthA * lengthB); // Update the maximum product
40 }
41 }
42 }
43 }
44
45 return maxProduct; // Return the final maximum product of palindromic subsequence lengths
46 }
47};
48
1// Function to compute the maximum product of the lengths of two non-overlapping palindromic subsequences
2function maxProduct(s: string): number {
3 const n: number = s.length; // Get the length of the input string
4 const isPalindrome: boolean[] = new Array(1 << n).fill(true); // Initialize an array to track if a subsequence is a palindrome
5
6 // Check each subsequence represented by a bitmask to see if it is a palindrome
7 for (let mask = 1; mask < (1 << n); ++mask) {
8 let left = 0, right = n - 1;
9 while (left < right) {
10 // Advance the left index until it points to a character included in the subsequence
11 while (left < right && !((mask >> left) & 1)) {
12 ++left;
13 }
14 // Move the right index back until it points to a character included in the subsequence
15 while (left < right && !((mask >> right) & 1)) {
16 --right;
17 }
18 // If the characters at the current left and right indices do not match, this is not a palindrome
19 if (left < right && s[left] !== s[right]) {
20 isPalindrome[mask] = false;
21 break;
22 }
23 left++;
24 right--;
25 }
26 }
27
28 let maxProduct = 0; // Initialize the maximum product to 0
29
30 // Iterate over all bitmasks to find the maximum product of palindromic subsequence pairs
31 for (let i = 1; i < (1 << n); ++i) {
32 if (isPalindrome[i]) { // Only consider the bitmask if it represents a palindrome
33 const lengthA = bitCount(i); // Compute the length of palindrome A
34 const complementMask = ((1 << n) - 1) ^ i; // Generate a bitmask for the complementary subsequence
35
36 // Find the other palindromic subsequence with the maximum length that can pair with the current one
37 for (let j = complementMask; j; j = (j - 1) & complementMask) {
38 if (isPalindrome[j]) {
39 const lengthB = bitCount(j); // Compute the length of palindrome B
40 maxProduct = Math.max(maxProduct, lengthA * lengthB); // Update the maximum product
41 }
42 }
43 }
44 }
45
46 return maxProduct; // Return the final maximum product
47}
48
49// Function to count the number of set bits in a bitmask (equivalent to __builtin_popcount in C++)
50function bitCount(mask: number): number {
51 let count = 0;
52 while (mask) {
53 count += mask & 1;
54 mask >>= 1;
55 }
56 return count;
57}
58
Time and Space Complexity
The time complexity of the code above can be analyzed as follows:
-
The first for loop, running from
k
inrange(1, 1 << n)
, enumerates all possible subsets of the strings
wheren
is the length ofs
. For each subset, the while loop checks if it forms a palindrome, which takesO(n)
time in the worst case. The number of subsets is2^n
, so this part of the code runs inO(n * 2^n)
time. -
The second part of the code contains two nested loops. The outer loop runs for
2^n - 1
iterations, and for each iteration, the inner while loop potentially runs multiple times. The maximal number of times the inner loop can run can be approximated by2^n
again because it starts atmx
and decreases until it reaches0
. However, the average number of iterations is less due to the bitwise AND operation withmx
. Since the exact number of iterations is hard to determine without a deeper analysis of the distribution of palindromes, we can approximate the time complexity of the inner loop with the upper bound ofO(2^n)
as well. The calculation within the loop includes bit count (O(log n)
) and a max operation (O(1)
), which are considerably less thanO(2^n)
, so they don't affect the overall time complexity. Thus, the second part of the code runs inO(2^n * 2^n)
time.
The space complexity is determined by:
-
The boolean array
p
of size2^n
, which results in a space complexity ofO(2^n)
. -
The variables and constant space usage inside the loops do not contribute to the space complexity significantly as compared to
p
.
Therefore, the total time complexity of the algorithm can be estimated as O(n * 2^n + 2^n * 2^n)
which simplifies to O(2^n * 2^n)
because 2^n * 2^n
dominates n * 2^n
. The space complexity is O(2^n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.