Maximum Product of the Length of Two Palindromic Subsequences

Med

#1824Time: 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: 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.

Patterns

Dynamic Programming Backtracking Bit Manipulation Bitmask

Data structures

String

Prompt

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 1st subsequence and "cdc" for the 2nd 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 1st subsequence and "b" (the second character) for the 2nd 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 1st subsequence and "xxcxx" for the 2nd subsequence.
The product of their lengths is: 5 * 5 = 25.

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1class Solution {2    public int maxProduct(String s) {3        int n = s.length();4        Map<Integer, Integer> palindromeLengths = new HashMap<>();5 6        for (int mask = 1; mask < (1 << n); mask++) {7            StringBuilder sub = new StringBuilder();8            for (int i = 0; i < n; i++) {9                if ((mask & (1 << i)) != 0) {10                    sub.append(s.charAt(i));11                }12            }13            if (isPalindrome(sub.toString())) {14                palindromeLengths.put(mask, sub.length());15            }16        }17 18        int maxProd = 0;19        List<Integer> masks = new ArrayList<>(palindromeLengths.keySet());20        for (int i = 0; i < masks.size(); i++) {21            for (int j = i; j < masks.size(); j++) {22                int mask1 = masks.get(i);23                int mask2 = masks.get(j);24                if ((mask1 & mask2) == 0) {25                    int product = palindromeLengths.get(mask1) * palindromeLengths.get(mask2);26                    maxProd = Math.max(maxProd, product);27                }28            }29        }30        return maxProd;31    }32 33    private boolean isPalindrome(String str) {34        int left = 0, right = str.length() - 1;35        while (left < right) {36            if (str.charAt(left) != str.charAt(right)) {37                return false;38            }39            left++;40            right--;41        }42        return true;43    }44}

Complexity

Time

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

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.

Trade-offs

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.

This approach uses recursion (backtracking) to explore all possible ways to partition the characters of the string s into three groups: one for the first subsequence, one for the second, and one for unused characters.

Algorithm

Initialize a global variable maxProduct = 0.
Define a recursive function backtrack(index, s1, s2):
- Base Case: If index == s.length():
  - If s1 is a palindrome and s2 is a palindrome:
    - maxProduct = max(maxProduct, s1.length() * s2.length()).
  - Return.
- Recursive Step:
  - Choice 1 (add to s1): backtrack(index + 1, s1 + s.charAt(index), s2).
  - Choice 2 (add to s2): backtrack(index + 1, s1, s2 + s.charAt(index)).
  - Choice 3 (ignore): backtrack(index + 1, s1, s2).
Start the process by calling backtrack(0, "", "").
Return maxProduct.
Using StringBuilder instead of string concatenation is recommended for better performance.

Walkthrough

We define a recursive function, say backtrack(index, s1, s2), that tries to build two disjoint subsequences, s1 and s2. The index parameter tracks the current character in s being considered. For each character s.charAt(index), we have three choices:

Append it to s1.
Append it to s2.
Ignore it (don't add to either s1 or s2). The recursion proceeds by making one of these three choices and then calling itself for the next index, index + 1. The base case for the recursion is when index reaches the end of the string s. At this point, we have formed two complete (though possibly empty) subsequences, s1 and s2. We check if both are palindromes. If they are, we calculate the product of their lengths and update a global maximum.

1class Solution {2    int maxProd = 0;3 4    public int maxProduct(String s) {5        backtrack(0, s, new StringBuilder(), new StringBuilder());6        return maxProd;7    }8 9    private void backtrack(int index, String s, StringBuilder s1, StringBuilder s2) {10        if (index == s.length()) {11            if (isPalindrome(s1) && isPalindrome(s2)) {12                maxProd = Math.max(maxProd, s1.length() * s2.length());13            }14            return;15        }16 17        char c = s.charAt(index);18 19        // Choice 1: Add to s120        s1.append(c);21        backtrack(index + 1, s, s1, s2);22        s1.deleteCharAt(s1.length() - 1); // backtrack23 24        // Choice 2: Add to s225        s2.append(c);26        backtrack(index + 1, s, s1, s2);27        s2.deleteCharAt(s2.length() - 1); // backtrack28 29        // Choice 3: Ignore30        backtrack(index + 1, s, s1, s2);31    }32 33    private boolean isPalindrome(StringBuilder sb) {34        if (sb.length() == 0) return true;35        int left = 0, right = sb.length() - 1;36        while (left < right) {37            if (sb.charAt(left) != sb.charAt(right)) {38                return false;39            }40            left++;41            right--;42        }43        return true;44    }45}

Complexity

Time

O(n * 3^n). There are `3^n` possible partitions. For each partition, we perform two palindrome checks, which take `O(n)` time in total.

Space

O(n). The recursion depth is `n`, and the `StringBuilder`s also take `O(n)` space.

Trade-offs

Pros

Relatively simple to implement and understand.
It directly maps to the problem's combinatorial nature.

Cons

Can be slow for larger n, though it's acceptable for n <= 12.

This is the most efficient approach. It leverages bitmasking to represent subsequences and dynamic programming to avoid redundant computations. The core idea is to first precompute the lengths of all palindromic subsequences and then efficiently find the best pair.

Algorithm

Initialize n = s.length().
Create an array dp of size (1 << n).
Iterate mask from 1 to (1 << n) - 1:
- Construct subsequence sub from s using mask.
- If sub is a palindrome, set dp[mask] = sub.length().
For i from 0 to n-1:
- For mask from 1 to (1 << n) - 1:
  - If the i-th bit of mask is set ((mask >> i) & 1 == 1):
    - dp[mask] = max(dp[mask], dp[mask ^ (1 << i)]).
Initialize maxProduct = 0.
Iterate mask1 from 1 to (1 << n) - 1:
- mask2 = ((1 << n) - 1) ^ mask1.
- product = dp[mask1] * dp[mask2].
- maxProduct = max(maxProduct, product).
Return maxProduct.

Walkthrough

The approach consists of three main steps:

Precompute Palindrome Lengths: We iterate through all 2^n masks. For each mask, we generate the corresponding subsequence and check if it's a palindrome. We store the length of the subsequence if it is a palindrome, and 0 otherwise, in an array dp of size 2^n. dp[mask] will hold the length.
DP on Subsets: We want to find, for each mask, the length of the longest palindromic subsequence that is a submask of it. We can compute this using a DP technique. Let dp[mask] be the length of the longest palindromic subsequence that can be formed using a subset of characters represented by mask. We can compute this dp array as follows:
- Initialize dp[mask] with the length if the subsequence for mask is a palindrome, 0 otherwise.
- Then, for each bit i from 0 to n-1, we iterate through all masks. If the i-th bit is set in a mask, it means the character s.charAt(i) is included. The longest palindrome for this mask is either one that includes s.charAt(i) or one that doesn't. The latter is dp[mask ^ (1 << i)]. So, we update dp[mask] = max(dp[mask], dp[mask ^ (1 << i)]). This propagates the maximum lengths from submasks to their supermasks.
Find Maximum Product: After computing the dp array, dp[mask] contains the length of the longest palindromic subsequence for any submask of mask. We can now iterate through all possible masks mask1 from 1 to (1 << n) - 1. For each mask1, we consider it for the first subsequence. The remaining characters are represented by the complement mask, mask2 = ((1 << n) - 1) ^ mask1. The length of the longest palindromic subsequence from mask1 is dp[mask1], and from mask2 is dp[mask2]. We calculate their product and update the overall maximum.

1class Solution {2    public int maxProduct(String s) {3        int n = s.length();4        int N = 1 << n;5        int[] dp = new int[N];6 7        for (int mask = 1; mask < N; mask++) {8            StringBuilder sub = new StringBuilder();9            for (int i = 0; i < n; i++) {10                if ((mask & (1 << i)) != 0) {11                    sub.append(s.charAt(i));12                }13            }14            if (isPalindrome(sub.toString())) {15                dp[mask] = sub.length();16            }17        }18 19        for (int i = 0; i < n; i++) {20            for (int mask = 1; mask < N; mask++) {21                if ((mask & (1 << i)) != 0) {22                    dp[mask] = Math.max(dp[mask], dp[mask ^ (1 << i)]);23                }24            }25        }26 27        int maxProd = 0;28        for (int mask1 = 1; mask1 < N; mask1++) {29            int mask2 = (N - 1) ^ mask1;30            maxProd = Math.max(maxProd, dp[mask1] * dp[mask2]);31        }32 33        return maxProd;34    }35 36    private boolean isPalindrome(String str) {37        int left = 0, right = str.length() - 1;38        while (left < right) {39            if (str.charAt(left) != str.charAt(right)) {40                return false;41            }42            left++;43            right--;44        }45        return true;46    }47}

Complexity

Time

O(n * 2^n). Precomputing palindrome lengths takes O(n * 2^n). The DP on subsets step takes O(n * 2^n). The final loop takes O(2^n). The total is dominated by O(n * 2^n).

Space

O(2^n) for the `dp` array.

Trade-offs

Pros

Highly efficient and guaranteed to pass within time limits for the given constraints.

Cons

More complex to understand and implement, requiring knowledge of bitmasking and dynamic programming on subsets.

Solutions

Solution

1class Solution {2public3  int maxProduct(String s) {4    int n = s.length();5    boolean[] p = new boolean[1 << n];6    Arrays.fill(p, true);7    for (int k = 1; k < 1 << n; ++k) {8      for (int i = 0, j = n - 1; i < n; ++i, --j) {9        while (i < j && (k >> i & 1) == 0) {10          ++i;11        }12        while (i < j && (k >> j & 1) == 0) {13          --j;14        }15        if (i < j && s.charAt(i) != s.charAt(j)) {16          p[k] = false;17          break;18        }19      }20    }21    int ans = 0;22    for (int i = 1; i < 1 << n; ++i) {23      if (p[i]) {24        int a = Integer.bitCount(i);25        int mx = ((1 << n) - 1) ^ i;26        for (int j = mx; j > 0; j = (j - 1) & mx) {27          if (p[j]) {28            int b = Integer.bitCount(j);29            ans = Math.max(ans, a * b);30          }31        }32      }33    }34    return ans;35  }36}

1class Solution {2public:3  int maxProduct(string s) {4    int n = s.size();5    vector<bool> p(1 << n, true);6    for (int k = 1; k < 1 << n; ++k) {7      for (int i = 0, j = n - 1; i < j; ++i, --j) {8        while (i < j && !(k >> i & 1)) {9          ++i;10        }11        while (i < j && !(k >> j & 1)) {12          --j;13        }14        if (i < j && s[i] != s[j]) {15          p[k] = false;16          break;17        }18      }19    }20    int ans = 0;21    for (int i = 1; i < 1 << n; ++i) {22      if (p[i]) {23        int a = __builtin_popcount(i);24        int mx = ((1 << n) - 1) ^ i;25        for (int j = mx; j; j = (j - 1) & mx) {26          if (p[j]) {27            int b = __builtin_popcount(j);28            ans = max(ans, a * b);29          }30        }31      }32    }33    return ans;34  }35};

1class Solution:2    def maxProduct(self, s: str) -> int: n = len(s) p = [True] * (1 << n) for k in range(1, 1 << n): i, j = 0, n - 1 while i < j: while i < j and (k >> i & 1) == 0: i += 1 while i < j and (k >> j & 1) == 0: j -= 1 if i < j and s[i] != s[j]: p[k] = False break i, j = i + 1, j - 1 ans = 0 for i in range(1, 1 << n): if p[i]: mx = ((1 << n) - 1) ^ i j = mx a = i . bit_count() while j: if p[j]: b = j . bit_count() ans = max(ans, a * b) j = (j - 1) & mx return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int maxProduct(String s) {4    int n = s.length();5    boolean[] p = new boolean[1 << n];6    Arrays.fill(p, true);7    for (int k = 1; k < 1 << n; ++k) {8      for (int i = 0, j = n - 1; i < n; ++i, --j) {9        while (i < j && (k >> i & 1) == 0) {10          ++i;11        }12        while (i < j && (k >> j & 1) == 0) {13          --j;14        }15        if (i < j && s.charAt(i) != s.charAt(j)) {16          p[k] = false;17          break;18        }19      }20    }21    int ans = 0;22    for (int i = 1; i < 1 << n; ++i) {23      if (p[i]) {24        int a = Integer.bitCount(i);25        int mx = ((1 << n) - 1) ^ i;26        for (int j = mx; j > 0; j = (j - 1) & mx) {27          if (p[j]) {28            int b = Integer.bitCount(j);29            ans = Math.max(ans, a * b);30          }31        }32      }33    }34    return ans;35  }36}

1class Solution {2public:3  int maxProduct(string s) {4    int n = s.size();5    vector<bool> p(1 << n, true);6    for (int k = 1; k < 1 << n; ++k) {7      for (int i = 0, j = n - 1; i < j; ++i, --j) {8        while (i < j && !(k >> i & 1)) {9          ++i;10        }11        while (i < j && !(k >> j & 1)) {12          --j;13        }14        if (i < j && s[i] != s[j]) {15          p[k] = false;16          break;17        }18      }19    }20    int ans = 0;21    for (int i = 1; i < 1 << n; ++i) {22      if (p[i]) {23        int a = __builtin_popcount(i);24        int mx = ((1 << n) - 1) ^ i;25        for (int j = mx; j; j = (j - 1) & mx) {26          if (p[j]) {27            int b = __builtin_popcount(j);28            ans = max(ans, a * b);29          }30        }31      }32    }33    return ans;34  }35};

1class Solution:2    def maxProduct(self, s: str) -> int: n = len(s) p = [True] * (1 << n) for k in range(1, 1 << n): i, j = 0, n - 1 while i < j: while i < j and (k >> i & 1) == 0: i += 1 while i < j and (k >> j & 1) == 0: j -= 1 if i < j and s[i] != s[j]: p[k] = False break i, j = i + 1, j - 1 ans = 0 for i in range(1, 1 << n): if p[i]: mx = ((1 << n) - 1) ^ i j = mx a = i . bit_count() while j: if p[j]: b = j . bit_count() ans = max(ans, a * b) j = (j - 1) & mx return ans

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.