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

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

✓ Backtracking with Memoization

⏱️ Time: O(3ⁿ) Space: O(3ⁿ + n)

Use memoization to cache results of subproblems. Since we may encounter the same state multiple times during recursion, we can store the maximum product for each unique combination of remaining characters and current subsequences.

Bit Manipulation with Bitmask

⏱️ Time: O(3ⁿ × n) Space: O(n)

Instead of generating actual subsequences, use bitmasks to represent which characters belong to each subsequence. For each possible bitmask, check if the corresponding subsequences are palindromes and calculate their product.

Brute Force with Backtracking

⏱️ Time: O(3ⁿ) Space: O(n)

For each character in the string, we have three choices: assign it to the first subsequence, assign it to the second subsequence, or skip it. We recursively explore all possibilities and check if the resulting subsequences are palindromes.

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 (strlen(seq1) > 0 && strlen(seq2) > 0 && 
            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

Maximum Product of the Length of Two Palindromic Subsequences - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler