Maximum Product of the Length of Two Palindromic Subsequences - Video Solutions

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.