Maximum Product of the Length of Two Palindromic Subsequences

MEDIUM

Description

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.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "accbcaxxcxx"
Output: 25
Explanation: An optimal solution is to choose "accca" for the 1^st subsequence and "xxcxx" for the 2^nd subsequence.
The product of their lengths is: 5 * 5 = 25.

Constraints:

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

Approaches

Checkout 3 different approaches to solve Maximum Product of the Length of Two Palindromic Subsequences. Click on different approaches to view the approach and algorithm in detail.

Brute-Force with Bitmasking and Pairwise Check

This approach involves generating all possible subsequences of the input string s, checking which ones are palindromic, and then finding the best pair of disjoint palindromic subsequences by checking all pairs.

Algorithm

Initialize n = s.length().
Create a map palindromes to store (mask, length) for palindromic subsequences.
Iterate mask from 1 to (1 << n) - 1:
- Construct the subsequence sub from s using mask.
- If sub is a palindrome, put (mask, sub.length()) into palindromes.
Initialize maxProduct = 0.
Convert the keys of palindromes into a list pMasks.
Iterate through all pairs (mask1, mask2) from pMasks:
- If (mask1 & mask2) == 0 (the subsequences are disjoint):
  - product = palindromes.get(mask1) * palindromes.get(mask2).
  - maxProduct = max(maxProduct, product).
Return maxProduct.

Generate all subsequences: We can represent each subsequence using a bitmask of length n (where n is the length of s). A '1' at the i-th position in the mask means the character s.charAt(i) is included in the subsequence. We iterate through all 2^n possible masks.
Identify palindromic subsequences: For each mask, we construct the corresponding subsequence string. We then check if this string is a palindrome.
Store palindromes: We store the masks of all palindromic subsequences and their lengths, for example, in a hash map where the key is the mask and the value is the length.
Find the best pair: After identifying all palindromic subsequences, we iterate through all possible pairs of them. For each pair, we check if their corresponding masks are disjoint (i.e., their bitwise AND is zero). If they are disjoint, we calculate the product of their lengths and update our maximum product found so far.

class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        Map<Integer, Integer> palindromeLengths = new HashMap<>();

        for (int mask = 1; mask < (1 << n); mask++) {
            StringBuilder sub = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sub.append(s.charAt(i));
                }
            }
            if (isPalindrome(sub.toString())) {
                palindromeLengths.put(mask, sub.length());
            }
        }

        int maxProd = 0;
        List<Integer> masks = new ArrayList<>(palindromeLengths.keySet());
        for (int i = 0; i < masks.size(); i++) {
            for (int j = i; j < masks.size(); j++) {
                int mask1 = masks.get(i);
                int mask2 = masks.get(j);
                if ((mask1 & mask2) == 0) {
                    int product = palindromeLengths.get(mask1) * palindromeLengths.get(mask2);
                    maxProd = Math.max(maxProd, product);
                }
            }
        }
        return maxProd;
    }

    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n * 2^n + P^2), where P is the number of palindromic subsequences. In the worst case, P can be close to 2^n, making the complexity O(n * 2^n + 4^n). For n=12, this is computationally expensive.Space Complexity: O(P), where P is the number of palindromic subsequences. In the worst case, this can be O(2^n) to store the masks and lengths.

Pros and Cons

Pros:

Conceptually straightforward extension of generating all subsequences.

Cons:

The pairwise check can be very slow if there are many palindromic subsequences, leading to a high time complexity that might not pass for larger constraints.

Code Solutions

Checking out 3 solutions in different languages for Maximum Product of the Length of Two Palindromic Subsequences. Click on different languages to view the code.

class Solution {
public
  int maxProduct(String s) {
    int n = s.length();
    boolean[] p = new boolean[1 << n];
    Arrays.fill(p, true);
    for (int k = 1; k < 1 << n; ++k) {
      for (int i = 0, j = n - 1; i < n; ++i, --j) {
        while (i < j && (k >> i & 1) == 0) {
          ++i;
        }
        while (i < j && (k >> j & 1) == 0) {
          --j;
        }
        if (i < j && s.charAt(i) != s.charAt(j)) {
          p[k] = false;
          break;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i < 1 << n; ++i) {
      if (p[i]) {
        int a = Integer.bitCount(i);
        int mx = ((1 << n) - 1) ^ i;
        for (int j = mx; j > 0; j = (j - 1) & mx) {
          if (p[j]) {
            int b = Integer.bitCount(j);
            ans = Math.max(ans, a * b);
          }
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Maximum Product of the Length of Two Palindromic Subsequences

Patterns:

Dynamic ProgrammingBacktrackingBit ManipulationBitmask

Data Structures:

String