Back to solutions

Maximum Product of The Length of Two Palindromic Subsequences

MediumArrays

Pick two disjoint palindromic subsequences maximizing the product of lengths.

Open problem
Constraints
  • 2 <= length <= 12
  • lowercase English letters

Bitmask subsets

Time O(3^n)Space O(2^n)

With length up to 12 there are at most 2^12 subsets. Represent each subsequence as a bitmask of chosen indices and precompute which masks are palindromes and their lengths. Then for each palindrome mask, iterate over submasks of its complement (guaranteed disjoint) and take the best product of lengths.

Key terms
bitmask:
An integer whose set bits select a subset of indices.
submask enumeration:
Iterating over every subset of a given mask using b = (b-1) & mask.
disjoint:
The two subsequences share no index, ensured by picking the second from the complement.
int maxProduct(const string& s) {
    int n = s.size(), full = 1 << n;
    vector<int> palLen(full, 0);
    for (int m = 1; m < full; m++)
        if (isPalin(s, m)) palLen[m] = __builtin_popcount(m);
    int best = 0;
    for (int a = 1; a < full; a++) {
        if (!palLen[a]) continue;
        int comp = (full - 1) ^ a;
        for (int b = comp; b > 0; b = (b - 1) & comp)
            if (palLen[b]) best = max(best, palLen[a] * palLen[b]);
    }
    return best;
}
Step by step
  1. Enumerate all non-empty masks; record palindrome masks and their popcount length.
  2. For each palindrome mask a, compute its complement comp = all-bits XOR a.
  3. Enumerate every submask b of comp; if b is a palindrome, update best with len(a)*len(b).
  4. Return the best product found.