Problem Description

You are given a string s and need to find two disjoint palindromic subsequences from it such that the product of their lengths is maximized.

A subsequence is a string formed by deleting some (or no) characters from the original string without changing the order of the remaining characters. For example, "ace" is a subsequence of "abcde".

A string is palindromic if it reads the same forwards and backwards. For example, "aba" and "racecar" are palindromes.

Two subsequences are disjoint if they don't share any character at the same position in the original string. In other words, for any index i in string s, the character at position i can belong to at most one of the two subsequences.

Your task is to find two such disjoint palindromic subsequences where the product of their lengths is as large as possible, and return this maximum product.

For example, if s = "leetcodecom", one possible solution could be finding two palindromic subsequences like "ete" (length 3) and "cdc" (length 3), giving a product of 9. The actual maximum might be different, but this illustrates the concept of finding disjoint palindromic subsequences and calculating their length product.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves finding subsequences in a string, not traversing nodes and edges in a graph structure.

Need to solve for kth smallest/largest?

• No: We're looking for the maximum product of lengths, not the kth smallest or largest element.

Involves Linked Lists?

• No: The problem works with strings and subsequences, not linked list data structures.

Does the problem have small constraints?

• Yes: The string length is at most 12 characters (as mentioned in the solution approach). With such small constraints, we can enumerate all possible subsequences (2^12 = 4096 possibilities).

Brute force / Backtracking?

• Yes: Given the small constraints, we can use brute force to enumerate all possible ways to split the string into two disjoint subsequences. We need to:
  1. Generate all possible subsequences (using binary enumeration)
  2. Check which ones are palindromes
  3. For each palindromic subsequence, find all disjoint palindromic subsequences
  4. Calculate the product of their lengths and track the maximum

Conclusion: The flowchart correctly leads us to a brute force/backtracking approach. The small constraint (string length ≤ 12) makes it feasible to enumerate all 2^n possible subsequences using binary representation, where each bit indicates whether a character is included in the subsequence or not. This aligns perfectly with the provided solution that uses binary enumeration and bit manipulation to find all palindromic subsequences and their disjoint pairs.

Intuition

The key insight comes from recognizing that with a string length of at most 12, we have a manageable search space. Each character can either be included or excluded from a subsequence, giving us 2^12 = 4096 possible subsequences - small enough to check exhaustively.

We can represent each subsequence as a binary number where bit i indicates whether character i is included. For example, with string "abc", the binary number 101 represents the subsequence "ac" (taking characters at positions 0 and 2).

The challenge is finding two disjoint palindromic subsequences. Two subsequences are disjoint if they don't share any character at the same position. In binary terms, if subsequence i has certain bits set to 1, then any disjoint subsequence j must have those bits set to 0. This means i & j = 0 (no overlapping bits).

Here's the clever part: once we identify a palindromic subsequence with bitmask i, we know that any disjoint subsequence must come from the complement of i. The complement is (2^n - 1) ^ i, which gives us all the bits that are NOT set in i. Any valid disjoint subsequence j must be a subset of this complement.

So our approach becomes:

1. Pre-compute which subsequences are palindromes by checking each bitmask
2. For each palindromic subsequence i, enumerate all possible subsequences from its complement
3. Check if those complement subsequences are also palindromes
4. If both are palindromes and disjoint, calculate the product of their lengths (number of 1-bits in each mask)
5. Track the maximum product found

This binary enumeration approach elegantly handles the constraint checking and ensures we explore all valid pairs of disjoint palindromic subsequences.

Learn more about Dynamic Programming, Backtracking and Bitmask patterns.

Solution Approach

The implementation uses binary enumeration to explore all possible subsequences efficiently.

Step 1: Pre-compute Palindromic Subsequences

First, we create a boolean array p of size 2^n where p[k] indicates whether the subsequence represented by bitmask k is a palindrome.

For each bitmask k from 1 to 2^n - 1:

• Use two pointers i (starting at 0) and j (starting at n-1)
• Skip positions where the bit is 0 (character not included in subsequence)
• Check if characters at included positions form a palindrome by comparing s[i] and s[j]
• If any mismatch is found, mark p[k] = False

for k in range(1, 1 << n):
    i, j = 0, n - 1
    while i < j:
        # Skip unselected characters from left
        while i < j and (k >> i & 1) == 0:
            i += 1
        # Skip unselected characters from right
        while i < j and (k >> j & 1) == 0:
            j -= 1
        # Check palindrome property
        if i < j and s[i] != s[j]:
            p[k] = False
            break
        i, j = i + 1, j - 1

Step 2: Find Maximum Product

For each palindromic subsequence i:

1. Calculate its complement: mx = ((1 << n) - 1) ^ i
   • This gives all positions not used by subsequence i
2. Enumerate all subsets j of the complement mx
   • Use the technique j = (j - 1) & mx to iterate through subsets
3. If j is also palindromic, calculate the product of lengths
   • Length is the bit count (number of 1s) in the bitmask
   • Use bit_count() method to count 1s efficiently

for i in range(1, 1 << n):
    if p[i]:  # If i is palindromic
        mx = ((1 << n) - 1) ^ i  # Complement of i
        j = mx
        a = i.bit_count()  # Length of first palindrome
        while j:
            if p[j]:  # If j is also palindromic
                b = j.bit_count()  # Length of second palindrome
                ans = max(ans, a * b)  # Update maximum product
            j = (j - 1) & mx  # Next subset of mx

The clever bit manipulation j = (j - 1) & mx ensures we only iterate through valid subsets of mx, guaranteeing that subsequences i and j remain disjoint throughout the enumeration.

Time Complexity: O(3^n) - For each of the 2^n subsequences, we potentially check 2^k disjoint subsequences where k is the number of remaining positions.

Space Complexity: O(2^n) - To store the palindrome status of all subsequences.

Example Walkthrough

Let's walk through the solution with s = "abab" (n = 4).

Step 1: Pre-compute which subsequences are palindromes

We'll check all 15 non-empty subsequences (bitmasks 1 to 15):

• Bitmask 0001 (binary) = 1: subsequence "b" (position 3) → palindrome ✓
• Bitmask 0010 (binary) = 2: subsequence "a" (position 2) → palindrome ✓
• Bitmask 0011 (binary) = 3: subsequence "ab" (positions 2,3) → NOT palindrome ✗
• Bitmask 0100 (binary) = 4: subsequence "b" (position 1) → palindrome ✓
• Bitmask 0101 (binary) = 5: subsequence "bb" (positions 1,3) → palindrome ✓
• Bitmask 0110 (binary) = 6: subsequence "ba" (positions 1,2) → NOT palindrome ✗
• Bitmask 0111 (binary) = 7: subsequence "bab" (positions 1,2,3) → palindrome ✓
• Bitmask 1000 (binary) = 8: subsequence "a" (position 0) → palindrome ✓
• Bitmask 1001 (binary) = 9: subsequence "ab" (positions 0,3) → NOT palindrome ✗
• Bitmask 1010 (binary) = 10: subsequence "aa" (positions 0,2) → palindrome ✓
• Bitmask 1011 (binary) = 11: subsequence "aab" (positions 0,2,3) → NOT palindrome ✗
• Bitmask 1100 (binary) = 12: subsequence "ab" (positions 0,1) → NOT palindrome ✗
• Bitmask 1101 (binary) = 13: subsequence "abb" (positions 0,1,3) → NOT palindrome ✗
• Bitmask 1110 (binary) = 14: subsequence "aba" (positions 0,1,2) → palindrome ✓
• Bitmask 1111 (binary) = 15: subsequence "abab" (all positions) → NOT palindrome ✗

So palindromic subsequences are: {1, 2, 4, 5, 7, 8, 10, 14}

Step 2: Find disjoint palindromic pairs

Let's trace through finding disjoint pairs for bitmask i = 10 (binary 1010, subsequence "aa"):

1. Calculate complement: mx = 15 ^ 10 = 5 (binary 0101)

   • This represents positions 1 and 3 (the "b" characters)

2. Enumerate subsets of mx = 5:

   • j = 5 (binary 0101, "bb"): Is palindrome? Yes!
     • Product = 2 × 2 = 4
   • j = 4 (binary 0100, "b" at position 1): Is palindrome? Yes!
     • Product = 2 × 1 = 2
   • j = 1 (binary 0001, "b" at position 3): Is palindrome? Yes!
     • Product = 2 × 1 = 2
   • j = 0: Stop (empty subsequence)

Let's check another example with i = 7 (binary 0111, subsequence "bab"):

1. Calculate complement: mx = 15 ^ 7 = 8 (binary 1000)

   • This represents position 0 (the first "a")

2. Enumerate subsets of mx = 8:

   • j = 8 (binary 1000, "a"): Is palindrome? Yes!
     • Product = 3 × 1 = 3

Step 3: Find maximum product

After checking all pairs:

• "aa" (10) and "bb" (5): product = 2 × 2 = 4 ← Maximum!
• "bab" (7) and "a" (8): product = 3 × 1 = 3
• "aba" (14) and "b" (1): product = 3 × 1 = 3
• And other combinations...

The maximum product is 4, achieved by selecting the disjoint palindromic subsequences "aa" and "bb".

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^n × n + 3^n)

The time complexity consists of two main parts:

1. First loop (preprocessing palindrome check): O(2^n × n)

   • The outer loop iterates through all 2^n - 1 possible subsequences (from 1 to 2^n - 1)
   • For each subsequence k, the inner while loops check if it forms a palindrome by comparing characters at positions i and j
   • In the worst case, checking each subsequence takes O(n) time as we traverse through the string positions
   • Total: O(2^n × n)

2. Second loop (finding maximum product): O(3^n)

   • The outer loop iterates through all 2^n - 1 possible subsequences
   • For each palindromic subsequence i, we iterate through all subsequences j that don't overlap with i
   • The key insight: for each bit position in the n-bit representation, we have 3 choices:
     • The bit belongs to subsequence i (fixed by outer loop)
     • The bit belongs to subsequence j (iterated in inner loop)
     • The bit belongs to neither subsequence
   • This gives us 3^n total combinations across all iterations
   • The operations inside (bit counting and max comparison) are O(1) or O(log n) which doesn't affect the dominant term

Space Complexity: O(2^n)

The space is dominated by the boolean array p which stores whether each of the 2^n possible subsequences is a palindrome. All other variables use constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Palindrome Checking for Subsequences

A critical pitfall is incorrectly checking whether a subsequence forms a palindrome. The naive approach of extracting characters and then checking palindrome property creates unnecessary overhead and potential errors.

Incorrect approach:

# Wrong: Building string then checking
chars = []
for i in range(n):
    if mask >> i & 1:
        chars.append(s[i])
# Then checking if chars forms palindrome

Correct approach: Use two pointers directly on the original string while skipping unselected positions:

left, right = 0, n - 1
while left < right:
    # Skip unselected positions
    while left < right and (mask >> left & 1) == 0:
        left += 1
    while left < right and (mask >> right & 1) == 0:
        right -= 1
    # Check palindrome property
    if left < right and s[left] != s[right]:
        is_palindrome[mask] = False
        break
    left += 1
    right -= 1

2. Missing Edge Case: Empty Subsequence

The code starts iteration from mask = 1, correctly skipping the empty subsequence (mask = 0). However, when iterating through submasks, forgetting to handle the case where second_mask becomes 0 could lead to issues.

Solution: The while loop while second_mask: naturally handles this by terminating when second_mask reaches 0.

3. Inefficient Submask Enumeration

Using a naive approach to find disjoint subsequences by checking all pairs would be O(4^n):

# Inefficient: Checking all pairs
for mask1 in range(1, 1 << n):
    for mask2 in range(1, 1 << n):
        if mask1 & mask2 == 0:  # Check if disjoint
            # Process...

Correct approach: Use complement and submask enumeration to guarantee disjoint subsequences:

complement = ((1 << n) - 1) ^ first_mask
second_mask = complement
while second_mask:
    # Process second_mask (guaranteed disjoint with first_mask)
    second_mask = (second_mask - 1) & complement

4. Bit Manipulation Errors

Common mistakes:

• Using mask >> i instead of mask >> i & 1 to check if bit i is set
• Incorrectly calculating complement as ~first_mask instead of ((1 << n) - 1) ^ first_mask
• The ~ operator in Python produces negative numbers for positive inputs, which causes issues

Solution: Always use ((1 << n) - 1) ^ mask for complement within n bits, and mask >> i & 1 to check individual bits.

5. Off-by-One Errors in Pointer Movement

When checking palindromes, forgetting to increment/decrement pointers after comparison:

# Wrong: Infinite loop if pointers don't move
if left < right and s[left] != s[right]:
    is_palindrome[mask] = False
    break
# Missing: left += 1, right -= 1

Solution: Always move pointers after each comparison to avoid infinite loops and ensure all character pairs are checked.