Maximum Product of the Length of Two Palindromic Subsequences

medium string bitmask palindrome

Problem

Given a string s (with 2 ≤ s.length ≤ 12 lowercase letters), pick two disjoint palindromic subsequences — they may not both use the same index — so that the product of their lengths is as large as possible. Return that maximum product.

A subsequence keeps characters in order but may drop some; it is palindromic if it reads the same forwards and backwards.

Inputs = "leetcodecom"

Output9

Choose "ete" and "cdc": both palindromes, disjoint, lengths 3 × 3 = 9.

s (2–12 lowercase letters)

def maxProduct(s):
    n = len(s)
    full = (1 << n) - 1
    is_pal = [False] * (1 << n)      # does this subset read as a palindrome?
    length = [0] * (1 << n)          # popcount = subsequence length
    # Precompute palindrome flag + length for every non-empty subset.
    for mask in range(1, 1 << n):
        idx = [i for i in range(n) if mask & (1 << i)]
        length[mask] = len(idx)
        lo, hi, ok = 0, len(idx) - 1, True
        while lo < hi:
            if s[idx[lo]] != s[idx[hi]]:
                ok = False
                break
            lo += 1
            hi -= 1
        is_pal[mask] = ok
    best = 0
    # Try each palindromic subset a, pair with palindromic subsets of its complement.
    for a in range(1, 1 << n):
        if not is_pal[a]:
            continue
        comp = full ^ a             # indices a did not use
        b = comp
        while b > 0:                # enumerate non-empty submasks of comp
            if is_pal[b]:
                best = max(best, length[a] * length[b])
            b = (b - 1) & comp
    return best

function maxProduct(s) {
  const n = s.length;
  const full = (1 << n) - 1;
  const isPal = new Array(1 << n).fill(false); // palindrome flag per subset
  const length = new Array(1 << n).fill(0);    // subsequence length per subset
  // Precompute palindrome flag + length for every non-empty subset.
  for (let mask = 1; mask < (1 << n); mask++) {
    const idx = [];
    for (let i = 0; i < n; i++) if (mask & (1 << i)) idx.push(i);
    length[mask] = idx.length;
    let lo = 0, hi = idx.length - 1, ok = true;
    while (lo < hi) {
      if (s[idx[lo]] !== s[idx[hi]]) { ok = false; break; }
      lo++; hi--;
    }
    isPal[mask] = ok;
  }
  let best = 0;
  // Try each palindromic subset a, pair with palindromic submasks of its complement.
  for (let a = 1; a < (1 << n); a++) {
    if (!isPal[a]) continue;
    const comp = full ^ a;        // indices a did not use
    for (let b = comp; b > 0; b = (b - 1) & comp) {
      if (isPal[b]) best = Math.max(best, length[a] * length[b]);
    }
  }
  return best;
}

int maxProduct(String s) {
    int n = s.length();
    int full = (1 << n) - 1;
    boolean[] isPal = new boolean[1 << n];   // palindrome flag per subset
    int[] length = new int[1 << n];          // subsequence length per subset
    // Precompute palindrome flag + length for every non-empty subset.
    for (int mask = 1; mask < (1 << n); mask++) {
        int[] idx = new int[Integer.bitCount(mask)];
        int t = 0;
        for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) idx[t++] = i;
        length[mask] = idx.length;
        int lo = 0, hi = idx.length - 1; boolean ok = true;
        while (lo < hi) {
            if (s.charAt(idx[lo]) != s.charAt(idx[hi])) { ok = false; break; }
            lo++; hi--;
        }
        isPal[mask] = ok;
    }
    int best = 0;
    // Try each palindromic subset a, pair with palindromic submasks of its complement.
    for (int a = 1; a < (1 << n); a++) {
        if (!isPal[a]) continue;
        int comp = full ^ a;                 // indices a did not use
        for (int b = comp; b > 0; b = (b - 1) & comp) {
            if (isPal[b]) best = Math.max(best, length[a] * length[b]);
        }
    }
    return best;
}

int maxProduct(string s) {
    int n = s.size();
    int full = (1 << n) - 1;
    vector<bool> isPal(1 << n, false);   // palindrome flag per subset
    vector<int> length(1 << n, 0);        // subsequence length per subset
    // Precompute palindrome flag + length for every non-empty subset.
    for (int mask = 1; mask < (1 << n); mask++) {
        vector<int> idx;
        for (int i = 0; i < n; i++) if (mask & (1 << i)) idx.push_back(i);
        length[mask] = idx.size();
        int lo = 0, hi = (int)idx.size() - 1; bool ok = true;
        while (lo < hi) {
            if (s[idx[lo]] != s[idx[hi]]) { ok = false; break; }
            lo++; hi--;
        }
        isPal[mask] = ok;
    }
    int best = 0;
    // Try each palindromic subset a, pair with palindromic submasks of its complement.
    for (int a = 1; a < (1 << n); a++) {
        if (!isPal[a]) continue;
        int comp = full ^ a;             // indices a did not use
        for (int b = comp; b > 0; b = (b - 1) & comp) {
            if (isPal[b]) best = max(best, length[a] * length[b]);
        }
    }
    return best;
}

Explanation

Because the string is tiny (at most 12 characters), we can afford to look at every subset of indices. Each subset is encoded as a bitmask: bit i set means we pick character s[i] into that subsequence. With n characters there are 2ⁿ subsets, at most 4096.

First we precompute two tables over all subsets: length[mask] is the number of chosen characters (the popcount), and is_pal[mask] says whether the chosen characters — read in index order — form a palindrome. We check that with two pointers walking inward from both ends.

Then for the answer we pick a first palindromic subsequence a. The two subsequences must be disjoint, so the second one may only use indices a left untouched — exactly the complement comp = full ^ a. We enumerate every non-empty submask b of comp using the trick b = (b - 1) & comp, and whenever b is also a palindrome we update best with length[a] × length[b].

The submask-enumeration trick visits exactly the subsets contained in comp, so disjointness is guaranteed for free — no index is shared between a and b.

For s = "leetcodecom" the best pair is "ete" (length 3) and "cdc" (length 3), giving the product 3 × 3 = 9.

Time: O(3ⁿ) Space: O(2ⁿ)