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.

Intuition

The intuition behind the solution involves the following steps:

  1. Generate all possible subsequences of the string.
  2. Check which of these subsequences are palindromic.
  3. Attempt to pair each palindromic subsequence with another, ensuring they do not overlap (disjoint).
  4. 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:

  1. 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 to 1 represents the inclusion of that character in the subsequence, while 0 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 in p are set to True.
    • 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 to False and the loop breaks, indicating that this subsequence is not palindromic.
  2. Find Maximized Product of Lengths:

    • With all palindromic subsequences identified, we loop through them with the bitmask i. The bitmask mx is computed as the XOR of i with the bitmask representing all characters in the string (i.e., (1 << n) - 1). This essentially inverts i, marking all indices not included in i.
    • Then, we initialize j with mx and enter a nested loop. Inside this loop, we only consider bitmasks j 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 bitmasks i and j (stored in variables a and b, respectively).
    • The product of a and b is calculated and checked against the current maximum product ans. If it is larger, it becomes the new maximum.
  3. 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 decrementing j at each step using j = (j - 1) & mx. By ANDing with mx, we ensure we get smaller bitmasks that represent subsequences disjoint from subsequence i.
  4. Return Result:

    • After all combinations are checked, the maximum product calculated is stored in ans, which is returned as the result.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example 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.

  1. Precompute Palindromic Subsequences:

    • First, we generate all possible subsequences using bit masks. For the string s = "ababa" which has a length of 5, we will have 2^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 or False). For our example:
      • p[5] = True since the bitmask 5 (00101) is palindromic.
      • p[10] = False for 10 (01010) because it's not palindromic.
      • p[20] = True for 20 (10100) since it's palindromic.
  2. 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 bitmask mx = 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 of 20 (10100) is 3 and the length of 3 (00011) is 2. The product is 3 * 2 = 6.
  3. Iterate Over All Combinations:

    • We keep decrementing j using j = (j - 1) & mx to find all smaller, non-overlapping palindromic subsequences.
    • For instance, if j was initially 11 (01111), the next j would be 7 (00111), representing the subsequence "aab", which is not palindromic.
  4. 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" (length 3) and "ab" (length 2).

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:

  1. The first for loop, running from k in range(1, 1 << n), enumerates all possible subsets of the string s where n is the length of s. For each subset, the while loop checks if it forms a palindrome, which takes O(n) time in the worst case. The number of subsets is 2^n, so this part of the code runs in O(n * 2^n) time.

  2. 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 by 2^n again because it starts at mx and decreases until it reaches 0. However, the average number of iterations is less due to the bitwise AND operation with mx. 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 of O(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 than O(2^n), so they don't affect the overall time complexity. Thus, the second part of the code runs in O(2^n * 2^n) time.

The space complexity is determined by:

  1. The boolean array p of size 2^n, which results in a space complexity of O(2^n).

  2. 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.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄