Maximum Product of the Length of Two Palindromic Subsequences solution and explanation
Google
8 more videos on this problem
Maximum Product of the Length of Two Palindromic Subsequences - Leetcode 2002 - PythonNeetCode · 16:47 · 21K views
Maximum Product of the Length of Two Palindromic Subsequences | (DP + Brute) | Leetcode Weekly 258Hitesh Tripathi · 12:45 · 2K views
Maximum Product of the Length of Two Palindromic Subsequences - BitMasking Tutorial - PythonCheatCode Ninja · 11:11 · 1K views
LeetCode 2002. Maximum Product of the Length of Two Palindromic SubsequencesHappy Coding · 13:57 · 964 views
【每日一题】LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences, 9/15/2021Huifeng Guan · 20:16 · 607 views
Leetcode 2002: Maximum Product of the Length of 2 Palindromic Subsequences | Master BacktrackingCode Concepts with Animesh · 22:51 · 596 views
2002. Maximum Product of the Length of Two Palindromic Subsequences (Leetcode Medium)Programming Live with Larry · 35:31 · 543 views
Maximum Product of the Length of Two Palindromic SubsequencesOwen Wu · 4:44 · 27 views
LeetCode 2002: Maximum Product of the Length of Two Palindromic SubsequencesAlitaCode · 25:09 · 8 views
The problem
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 <= 12sconsists of lowercase English letters only.
Approach overview
Problem Overview: Given a string s, choose two disjoint subsequences such that both are palindromes and the product of their lengths is maximized. The subsequences cannot reuse the same character index.
Approach 1: Brute Force with Bitmasking (O(n * 2^n + 4^n) time, O(2^n) space)
Represent every subsequence using a bitmask of length n. Iterate through all 2^n masks and build the subsequence by checking which bits are set. For each mask, verify whether the subsequence forms a palindrome using a two‑pointer check. Store the length for valid palindromes. Then compare every pair of masks and ensure they are disjoint using (mask1 & mask2) == 0. If both represent palindromes, update the maximum product of their lengths. This method demonstrates the core idea but becomes expensive due to checking every mask pair.
Approach 2: Bitmask Enumeration with Submask Optimization (O(n * 2^n + 3^n) time, O(2^n) space)
Still enumerate all subsequences using bitmasks, but store palindrome lengths in an array pal[mask]. For each mask that forms a palindrome, compute the complement mask representing unused indices. Instead of checking all masks again, iterate through only the submasks of the complement. This ensures both subsequences remain disjoint. The submask iteration reduces pair exploration to roughly 3^n states instead of 4^n. Bit operations make checks extremely fast and work well because the constraint on n is small.
Approach 3: Dynamic Programming with State Representation (O(n * 2^n + 3^n) time, O(2^n) space)
Use a DP-style state where each mask represents a subsequence. Precompute whether a mask forms a palindrome by constructing the sequence or by incrementally validating characters from both ends. Store its length if valid. Once the DP table is built, iterate through masks and enumerate submasks of the remaining characters to find the best partner subsequence. The DP state avoids recomputing palindrome checks repeatedly and keeps the solution efficient for strings up to length 12.
Bitmasking models subsequences naturally, while palindrome validation uses simple string checks. Problems involving subsequence enumeration and disjoint selection often combine bitmask techniques with backtracking ideas. Precomputing valid states is a classic pattern in dynamic programming over subsets.
Recommended for interviews: The bitmask approach with palindrome precomputation and submask enumeration is the expected solution. Interviewers want to see that you recognize the small constraint on n, model subsequences using bitmasks, and optimize pair checking using subset iteration. Starting with brute force shows understanding, but reaching the O(3^n) solution demonstrates strong problem‑solving skills.
Approach 1: Brute Force with Bitmasking
This approach utilizes bitmasking to enumerate all possible subsequences. Since the string length is constrained up to 12, we can afford to represent each subsequence with a bitmask. We will iterate over all combinations of two disjoint subsequences and check if each is palindromic before calculating the product of their lengths.
def is_palindrome(s, mask):
res = ''.join([s[i] for i in range(len(s)) if (mask & (1 << i))])
return res == res[::-1]
def count_bits(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
def max_product(s):
n = len(s)
max_product = 0
end = 1 << n
for mask1 in range(1, end):
if not is_palindrome(s, mask1):
continue
for mask2 in range(mask1 + 1, end):
if not is_palindrome(s, mask2) or (mask1 & mask2):
continue
max_product = max(max_product, count_bits(mask1) * count_bits(mask2))
return max_product
print(max_product("leetcodecom")) # Output should be 9public class MaxProduct {
public static boolean isPalindrome(char[] s, int mask) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length; i++) {
if ((mask & (1 << i)) != 0) {
sb.append(s[i]);
}
}
int l = 0, r = sb.length() - 1;
while (l < r) {
if (sb.charAt(l++) != sb.charAt(r--)) return false;
}
return true;
}
public static int countBits(int n) {
int count = 0;
while (n != 0) {
if ((n & 1) != 0) count++;
n >>= 1;
}
return count;
}
public static int maxProduct(String str) {
char[] s = str.toCharArray();
int maxProduct = 0;
int end = 1 << s.length;
for (int mask1 = 1; mask1 < end; mask1++) {
if (!isPalindrome(s, mask1)) continue;
for (int mask2 = mask1 + 1; mask2 < end; mask2++) {
if (!isPalindrome(s, mask2) || (mask1 & mask2) != 0) continue;
int product = countBits(mask1) * countBits(mask2);
maxProduct = Math.max(maxProduct, product);
}
}
return maxProduct;
}
public static void main(String[] args) {
System.out.println(maxProduct("leetcodecom")); // Output should be 9
}
}#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool is_palindrome(const string &s, int mask) {
string res = "";
for (int i = 0; i < s.size(); ++i) {
if (mask & (1 << i)) res += s[i];
}
int l = 0, r = res.size() - 1;
while (l < r) {
if (res[l++] != res[r--]) return false;
}
return true;
}
int count_bits(int n) {
int count = 0;
while (n) {
if (n & 1) count++;
n >>= 1;
}
return count;
}
int maxProduct(string s) {
int n = s.size();
int maxProduct = 0;
int end = 1 << n;
for (int mask1 = 1; mask1 < end; ++mask1) {
if (!is_palindrome(s, mask1)) continue;
for (int mask2 = mask1 + 1; mask2 < end; ++mask2) {
if (!is_palindrome(s, mask2) || (mask1 & mask2)) continue;
int product = count_bits(mask1) * count_bits(mask2);
maxProduct = max(maxProduct, product);
}
}
return maxProduct;
}
int main() {
string s = "leetcodecom";
cout << maxProduct(s) << endl; // Output should be 9
return 0;
}function isPalindrome(s, mask) {
let subsequence = '';
for (let i = 0; i < s.length; i++) {
if ((mask & (1 << i)) !== 0) {
subsequence += s[i];
}
}
for (let i = 0; i < Math.floor(subsequence.length / 2); i++) {
if (subsequence[i] !== subsequence[subsequence.length - 1 - i]) {
return false;
}
}
return true;
}
function countBits(n) {
let count = 0;
while (n !== 0) {
count += n & 1;
n >>= 1;
}
return count;
}
function maxProduct(s) {
const n = s.length;
let maxProduct = 0;
const end = 1 << n;
for (let mask1 = 1; mask1 < end; mask1++) {
if (!isPalindrome(s, mask1)) continue;
for (let mask2 = mask1 + 1; mask2 < end; mask2++) {
if (!isPalindrome(s, mask2) || (mask1 & mask2) !== 0) continue;
let product = countBits(mask1) * countBits(mask2);
maxProduct = Math.max(maxProduct, product);
}
}
return maxProduct;
}
console.log(maxProduct("leetcodecom")); // Output should be 9#include <stdio.h>
#include <string.h>
int is_palindrome(char* s, int mask) {
int len = strlen(s);
int l = 0, r = len - 1;
while (l < r) {
if (((mask >> l) & 1) == 0) l++;
else if (((mask >> r) & 1) == 0) r--;
else if (s[l] != s[r]) return 0;
else { l++; r--; }
}
return 1;
}
int count_bits(int n) {
int count = 0;
while (n) {
if (n & 1) count++;
n >>= 1;
}
return count;
}
int max_product(char* s) {
int n = strlen(s);
int end = (1 << n);
int max_product = 0;
for (int mask1 = 1; mask1 < end; mask1++) {
if (!is_palindrome(s, mask1)) continue;
for (int mask2 = mask1 + 1; mask2 < end; mask2++) {
if (!is_palindrome(s, mask2) || (mask1 & mask2) != 0) continue;
int product = count_bits(mask1) * count_bits(mask2);
if (product > max_product) max_product = product;
}
}
return max_product;
}
int main() {
char s[] = "leetcodecom";
printf("%d\n", max_product(s)); // Output should be 9
return 0;
}using System;
public class MaxProduct {
private static bool IsPalindrome(string s, int mask) {
var chars = new System.Text.StringBuilder();
for (int i = 0; i < s.Length; i++) {
if ((mask & (1 << i)) != 0) {
chars.Append(s[i]);
}
}
string res = chars.ToString();
for (int i = 0; i < res.Length / 2; i++) {
if (res[i] != res[res.Length - i - 1]) return false;
}
return true;
}
private static int CountBits(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
public static int MaxProduct(string s) {
int n = s.Length;
int maxProduct = 0;
int end = 1 << n;
for (int mask1 = 1; mask1 < end; mask1++) {
if (!IsPalindrome(s, mask1)) continue;
for (int mask2 = mask1 + 1; mask2 < end; mask2++) {
if (!IsPalindrome(s, mask2) || (mask1 & mask2) != 0) continue;
int product = CountBits(mask1) * CountBits(mask2);
maxProduct = Math.Max(maxProduct, product);
}
}
return maxProduct;
}
public static void Main() {
Console.WriteLine(MaxProduct("leetcodecom")); // Output should be 9
}
}This Python solution explores each possible mask permutation for subsequences and enforces its constraints. If valid, their product of lengths is evaluated, updating the maximum if required.
Time Complexity: O(2^n * n^2). Space Complexity: O(1).
Approach 2: Dynamic Programming with State Representation
This approach leverages dynamic programming to keep track of previously calculated states. Due to small problem size, it offers a compromise between recalculation and precomputation, making it swifter than combinatorial methods.
def max_product(s):
n = len(s)
dp = [0] * (1 << n)
for mask in range(1, 1 << n):
l, r = 0, n - 1
is_palindrome = True
while l < r:
while l < n and not ((mask >> l) & 1):
l += 1
while r >= 0 and not ((mask >> r) & 1):
r -= 1
if l < r and s[l] != s[r]:
is_palindrome = False
break
l += 1
r -= 1
if not is_palindrome:
continue
length = sum((mask >> i) & 1 for i in range(n))
dp[mask] = max(dp[mask], length)
result = 0
for mask1 in range(1, 1 << n):
if dp[mask1] == 0:
continue
for mask2 in range(1, 1 << n):
if dp[mask2] == 0 or (mask1 & mask2) != 0:
continue
result = max(result, dp[mask1] * dp[mask2])
return result
print(max_product("leetcodecom")) # Output should be 9import java.util.Arrays;
public class MaxProduct {
public static int maxProduct(String s) {
int n = s.length();
int[] dp = new int[1 << n];
for (int mask = 1; mask < (1 << n); mask++) {
int l = 0, r = n - 1;
boolean isPalindrome = true;
while (l < r) {
while (l < n && ((mask >> l) & 1) == 0) l++;
while (r >= 0 && ((mask >> r) & 1) == 0) r--;
if (l < r && s.charAt(l) != s.charAt(r)) {
isPalindrome = false;
break;
}
l++; r--;
}
if (!isPalindrome) continue;
int length = 0;
for (int i = 0; i < n; i++)
if (((mask >> i) & 1) != 0)
length++;
dp[mask] = Math.max(dp[mask], length);
}
int result = 0;
for (int mask1 = 1; mask1 < (1 << n); mask1++) {
if (dp[mask1] == 0) continue;
for (int mask2 = 1; mask2 < (1 << n); mask2++) {
if (dp[mask2] == 0 || (mask1 & mask2) != 0) continue;
result = Math.max(result, dp[mask1] * dp[mask2]);
}
}
return result;
}
public static void main(String[] args) {
System.out.println(maxProduct("leetcodecom")); // Output should be 9
}
}#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int max(int a, int b) { return a > b ? a : b; }
int maxProduct(string s) {
int n = s.size();
vector<int> dp(1 << n, 0);
for (int mask = 1; mask < (1 << n); mask++) {
int left = 0, right = n - 1;
int is_palindrome = 1;
while (left < right) {
while (left < n && !((mask >> left) & 1)) left++;
while (right >= 0 && !((mask >> right) & 1)) right--;
if (left < right && s[left] != s[right]) {
is_palindrome = 0;
break;
}
left++; right--;
}
if (!is_palindrome) continue;
int length = 0;
for (int i = 0; i < n; i++)
if ((mask >> i) & 1)
length++;
dp[mask] = max(dp[mask], length);
}
int result = 0;
for (int mask1 = 1; mask1 < (1 << n); mask1++) {
if (dp[mask1] == 0) continue;
for (int mask2 = 1; mask2 < (1 << n); mask2++) {
if (dp[mask2] == 0 || (mask1 & mask2) != 0) continue;
result = max(result, dp[mask1] * dp[mask2]);
}
}
return result;
}
int main() {
string s = "leetcodecom";
cout << maxProduct(s) << endl; // Output should be 9
return 0;
}function maxProduct(s) {
const n = s.length;
const dp = new Array(1 << n).fill(0);
for (let mask = 1; mask < (1 << n); mask++) {
let l = 0, r = n - 1;
let isPalindrome = true;
while (l < r) {
while (l < n && ((mask >> l) & 1) === 0) l++;
while (r >= 0 && ((mask >> r) & 1) === 0) r--;
if (l < r && s[l] !== s[r]) {
isPalindrome = false;
break;
}
l++; r--;
}
if (!isPalindrome) continue;
let length = 0;
for (let i = 0; i < n; i++)
if (((mask >> i) & 1) !== 0)
length++;
dp[mask] = Math.max(dp[mask], length);
}
let result = 0;
for (let mask1 = 1; mask1 < (1 << n); mask1++) {
if (dp[mask1] === 0) continue;
for (let mask2 = 1; mask2 < (1 << n); mask2++) {
if (dp[mask2] === 0 || (mask1 & mask2) !== 0) continue;
result = Math.max(result, dp[mask1] * dp[mask2]);
}
}
return result;
}
console.log(maxProduct("leetcodecom")); // Output should be 9#include <stdio.h>
#include <string.h>
int max(int a, int b) { return a > b ? a : b; }
int maxProduct(char *s) {
int n = strlen(s);
int dp[1 << n];
memset(dp, 0, sizeof(dp));
for (int mask = 1; mask < (1 << n); mask++) {
int left = 0, right = n - 1;
int is_palindrome = 1;
// Check if current mask represents a palindrome
while (left < right) {
while (left < n && !((mask >> left) & 1)) left++;
while (right >= 0 && !((mask >> right) & 1)) right--;
if (left < right && s[left] != s[right]) {
is_palindrome = 0;
break;
}
left++; right--;
}
if (!is_palindrome) continue;
// Calculate the number of bits (length of subsequence)
int length = 0;
for (int i = 0; i < n; i++)
if ((mask >> i) & 1)
length++;
dp[mask] = max(dp[mask], length);
}
int result = 0;
for (int mask1 = 1; mask1 < (1 << n); mask1++) {
if (dp[mask1] == 0) continue;
for (int mask2 = 1; mask2 < (1 << n); mask2++) {
if (dp[mask2] == 0 || (mask1 & mask2) != 0) continue;
result = max(result, dp[mask1] * dp[mask2]);
}
}
return result;
}
int main() {
char s[] = "leetcodecom";
printf("%d\n", maxProduct(s)); // Output should be 9
return 0;
}using System;
public class MaxProduct {
public static int MaxProduct(string s) {
int n = s.Length;
int[] dp = new int[1 << n];
for (int mask = 1; mask < (1 << n); mask++) {
int l = 0, r = n - 1;
bool isPalindrome = true;
while (l < r) {
while (l < n && ((mask >> l) & 1) == 0) l++;
while (r >= 0 && ((mask >> r) & 1) == 0) r--;
if (l < r && s[l] != s[r]) {
isPalindrome = false;
break;
}
l++; r--;
}
if (!isPalindrome) continue;
int length = 0;
for (int i = 0; i < n; i++)
if (((mask >> i) & 1) != 0)
length++;
dp[mask] = Math.Max(dp[mask], length);
}
int result = 0;
for (int mask1 = 1; mask1 < (1 << n); mask1++) {
if (dp[mask1] == 0) continue;
for (int mask2 = 1; mask2 < (1 << n); mask2++) {
if (dp[mask2] == 0 || (mask1 & mask2) != 0) continue;
result = Math.Max(result, dp[mask1] * dp[mask2]);
}
}
return result;
}
public static void Main() {
Console.WriteLine(MaxProduct("leetcodecom")); // Output should be 9
}
}This Python solution utilizes a dynamic programming array to manage possible subsequences and ensure palindromic conditions. It inspects the states' lengths and intersections with binary operators.
Time Complexity: O((3^n) * n). Space Complexity: O(2^n).
Approach 3: Binary Enumeration
We notice that the length of the string s does not exceed 12, so we can use the method of binary enumeration to enumerate all subsequences of s. Suppose the length of s is n, we can use 2^n binary numbers of length n to represent all subsequences of s. For each binary number, the i-th bit being 1 means the i-th character of s is in the subsequence, and 0 means it is not in the subsequence. For each binary number, we judge whether it is a palindrome subsequence and record it in the array p.
Next, we enumerate each number i in p. If i is a palindrome subsequence, then we can enumerate a number j from the complement of i, mx = (2^n - 1) \oplus i. If j is also a palindrome subsequence, then i and j are the two palindrome subsequences we are looking for. Their lengths are the number of 1s in the binary representation of i and j, denoted as a and b, respectively. Then their product is a times b. We take the maximum of all possible a times b.
The time complexity is (2^n times n + 3^n), and the space complexity is O(2^n). Here, n is the length of the string s.
func maxProduct(s string) (ans int) {
n := len(s)
p := make([]bool, 1<<n)
for i := range p {
p[i] = true
}
for k := 1; k < 1<<n; k++ {
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
for i < j && (k>>i&1) == 0 {
i++
}
for i < j && (k>>j&1) == 0 {
j--
}
if i < j && s[i] != s[j] {
p[k] = false
break
}
}
}
for i := 1; i < 1<<n; i++ {
if p[i] {
a := bits.OnesCount(uint(i))
mx := (1<<n - 1) ^ i
for j := mx; j > 0; j = (j - 1) & mx {
if p[j] {
b := bits.OnesCount(uint(j))
ans = max(ans, a*b)
}
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Bitmasking | Time Complexity: O(2^n * n^2). Space Complexity: O(1). |
| Dynamic Programming with State Representation | Time Complexity: O((3^n) * n). Space Complexity: O(2^n). |
| Binary Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Bitmask Pair Check | O(n * 2^n + 4^n) | O(2^n) | Conceptual baseline to understand subsequence enumeration and disjoint mask checks |
| Bitmask with Submask Enumeration | O(n * 2^n + 3^n) | O(2^n) | Best practical solution when string length is small (n ≤ 12) |
| Dynamic Programming on Bitmask States | O(n * 2^n + 3^n) | O(2^n) | When you want to cache palindrome states and avoid repeated validation |
Frequently asked questions
Is Maximum Product of the Length of Two Palindromic Subsequences easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 62%. The challenge comes from recognizing that the string length is small and that subsequences can be efficiently represented using bitmasks combined with subset enumeration.
Maximum Product of the Length of Two Palindromic Subsequences Python/Java solution
Implementations in Python, Java, C++, or JavaScript typically enumerate all bitmasks from 0 to 2^n - 1, check whether the mask forms a palindrome, and store its length. Then iterate through submasks of the unused indices to compute the maximum product of two palindromic subsequences.
How to solve Maximum Product of the Length of Two Palindromic Subsequences in O(n)?
An O(n) solution does not exist because the problem requires exploring subsequences. The best known approach uses subset enumeration with bitmasks, giving roughly O(3^n) time. Since the input size is small (n ≤ 12), this exponential technique remains practical.
What is the best approach for Maximum Product of the Length of Two Palindromic Subsequences?
The most efficient approach uses bitmasking to represent subsequences and precomputes which masks form palindromes. For each valid mask, iterate through submasks of the remaining characters to ensure the second subsequence is disjoint. This reduces the search to about O(3^n) states with O(2^n) memory, which works well for n ≤ 12.
Is Maximum Product of the Length of Two Palindromic Subsequences asked at Google/Amazon/Meta?
Palindrome subsequence and bitmask enumeration problems commonly appear in interviews at companies like Google, Amazon, and Meta. Variants that combine subsequences, bitmask DP, and palindrome checks are frequently used to test combinatorial optimization skills.
What data structure is used in Maximum Product of the Length of Two Palindromic Subsequences?
The main structure is a bitmask representing which characters are included in a subsequence. Arrays or hash maps store the palindrome length for each mask. Bit operations such as AND and submask iteration ensure the two subsequences remain disjoint.
What is the time complexity of Maximum Product of the Length of Two Palindromic Subsequences?
The optimized solution runs in O(n * 2^n + 3^n) time. The first part checks whether each mask forms a palindrome, and the second part enumerates submasks of the remaining characters to find the best disjoint partner subsequence. Space complexity is O(2^n) to store palindrome lengths.