Maximum Product of the Length of Two Palindromic Subsequences

Maximum Product of the Length of Two Palindromic Subsequences - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "leetcodecom"

› Output: 9

💡 Note: One optimal solution: subsequence 1 = "ete" (indices 1,2,7), subsequence 2 = "coc" (indices 4,5,10). Both are palindromes with lengths 3 and 3, giving product 3 × 3 = 9.

Example 2 — Short String

$ Input: s = "bb"

› Output: 1

💡 Note: The two subsequences must be disjoint, so we can only take one 'b' for each subsequence. Each has length 1, so the product is 1 × 1 = 1.

Example 3 — No Valid Palindromes

$ Input: s = "accbcaxxcxx"

› Output: 25

💡 Note: One optimal solution: subsequence 1 = "accca" (indices 0,1,2,4,5), subsequence 2 = "xxcxx" (indices 6,7,8,9,10). Both are palindromes with lengths 5 and 5, giving product 5 × 5 = 25.

Constraints

2 ≤ s.length ≤ 12
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string 'leetcodecom' with characters to assign

Split Assignment

Assign each character to subsequence 1, subsequence 2, or skip

Validate & Calculate

Check palindromes and find maximum product

Key Takeaway

🎯 Key Insight: Use backtracking to assign each character to one of two subsequences or skip it, then verify palindromes

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use backtracking or bit manipulation to try all possible ways to assign characters to two disjoint subsequences, then check if both form palindromes. The best approach uses memoization to cache repeated states. Time: O(3ⁿ), Space: O(3ⁿ)

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Memoization	O(3ⁿ)	O(3ⁿ + n)	Optimize backtracking by caching results for repeated states
Brute Force with Backtracking	O(3ⁿ)	O(n)	Try all possible ways to assign characters to two subsequences
Bit Manipulation with Bitmask	O(3ⁿ × n)	O(n)	Use bitmasks to represent all possible character assignments efficiently

Backtracking with Memoization — Algorithm Steps

Use recursion with state: current index and bitmasks for both subsequences
Cache results using memoization
Check palindrome property only at leaf nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate and store result

Cache Hit

Return stored result for same state

Optimization

Significant speedup from avoided recalculations

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_STATES 10000

struct MemoEntry {
    int index, mask1, mask2, result;
};

struct MemoEntry memo[MAX_STATES];
int memoSize = 0;
char s[20];
int n;

int isPalindrome(const char* str) {
    int len = strlen(str);
    int left = 0, right = len - 1;
    while (left < right) {
        if (str[left] != str[right]) return 0;
        left++;
        right--;
    }
    return 1;
}

int findMemo(int index, int mask1, int mask2) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].index == index && memo[i].mask1 == mask1 && memo[i].mask2 == mask2) {
            return memo[i].result;
        }
    }
    return -1;
}

void addMemo(int index, int mask1, int mask2, int result) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].index = index;
        memo[memoSize].mask1 = mask1;
        memo[memoSize].mask2 = mask2;
        memo[memoSize].result = result;
        memoSize++;
    }
}

int dp(int index, int mask1, int mask2) {
    if (index == n) {
        char seq1[20] = "", seq2[20] = "";
        
        for (int i = 0; i < n; i++) {
            if (mask1 & (1 << i)) {
                strncat(seq1, &s[i], 1);
            }
            if (mask2 & (1 << i)) {
                strncat(seq2, &s[i], 1);
            }
        }
        
        if (isPalindrome(seq1) && isPalindrome(seq2)) {
            return strlen(seq1) * strlen(seq2);
        }
        return 0;
    }
    
    int cached = findMemo(index, mask1, mask2);
    if (cached != -1) return cached;
    
    int choice1 = dp(index + 1, mask1 | (1 << index), mask2);
    int choice2 = dp(index + 1, mask1, mask2 | (1 << index));
    int choice3 = dp(index + 1, mask1, mask2);
    
    int result = choice1 > choice2 ? choice1 : choice2;
    result = result > choice3 ? result : choice3;
    
    addMemo(index, mask1, mask2, result);
    return result;
}

int solution(const char* str) {
    strcpy(s, str);
    n = strlen(s);
    memoSize = 0;
    return dp(0, 0, 0);
}

int main() {
    char s[20];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3ⁿ)

Each unique state is computed once, but there are still 3^n possible states

✓ Linear Growth

Space Complexity

O(3ⁿ + n)

Memoization table stores up to 3^n states plus recursion stack depth

⚡ Linearithmic Space

35.7K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler