We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Product of the Length of Two Palindromic Subsequences

Number: 2130

Difficulty: Medium

Paid? No

Companies: Microsoft, Ascend

Problem Description

Given a string s, find two disjoint palindromic subsequences where no character index is shared between them such that the product of their lengths is maximized. A subsequence is formed by deleting some or no characters from s without changing the order of the remaining characters, and a palindromic subsequence reads the same forwards and backwards.

Key Insights

  • Because the length of s is at most 12, the total number of subsequences (2^n) is manageable.
  • Represent each subsequence using a bit mask indicating the chosen indices.
  • Check if a subsequence is a palindrome by constructing the subsequence from the bit mask and comparing it to its reverse.
  • Store each valid mask along with its palindrome length.
  • Iterate over all pairs of masks; ensure they are disjoint (i.e., bitwise AND == 0) and maximize the product of their stored lengths.

Space and Time Complexity

Time Complexity: O(2^n * n + (2^n)^2)
Space Complexity: O(2^n)
(Note: n is the length of string s, which is at most 12)

Solution

The solution uses bit masking to enumerate all subsequences of s. For each possible bitmask from 0 to 2^n - 1:

  • Construct the subsequence using indices where the bitmask has a 1.
  • Check if the generated subsequence is a palindrome.
  • If yes, record the mask and its length. After processing all subsequences, use a double loop to iterate over pairs of valid masks. For each pair, check if the two bitmasks are disjoint (i.e., they do not share any index) by verifying (mask1 & mask2) == 0. If disjoint, compute the product of their lengths and update the maximum found product.

Code Solutions

# Function to determine if a given string is a palindrome
def is_palindrome(sub_str):
    return sub_str == sub_str[::-1]

def maxProduct(s: str) -> int:
    n = len(s)
    valid_masks = []  # List to store tuples of (mask, length of palindromic subsequence)
    
    # Enumerate all possible subsequences using bit masks
    for mask in range(1, 1 << n):
        subseq = []
        for i in range(n):
            # Check if the i-th bit is set in mask, then include s[i]
            if mask & (1 << i):
                subseq.append(s[i])
        subseq_str = ''.join(subseq)
        # If the subsequence is a palindrome, store the mask and its length
        if is_palindrome(subseq_str):
            valid_masks.append((mask, len(subseq_str)))
    
    max_product = 0
    # Compare every pair of palindromic subsequences to check for disjoint masks
    for i in range(len(valid_masks)):
        mask1, len1 = valid_masks[i]
        for j in range(i + 1, len(valid_masks)):
            mask2, len2 = valid_masks[j]
            # Check that the two masks do not share any common index
            if mask1 & mask2 == 0:
                max_product = max(max_product, len1 * len2)
    
    return max_product

# Example usage:
if __name__ == "__main__":
    s = "leetcodecom"
    print("Max product:", maxProduct(s))  # Expected Output: 9
← Back to All Questions