  The 2-LCPS problem, first introduced by Chowdhury et al. [Fundam. Inform.,
129(4):329-340, 2014], asks one to compute (the length of) a longest
palindromic common subsequence between two given strings $A$ and $B$. We show
that the 2-LCPS problem is at least as hard as the well-studied longest common
subsequence problem for four strings (the 4-LCS problem). Then, we present a
new algorithm which solves the 2-LCPS problem in $O(\sigma M^2 + n)$ time,
where $n$ denotes the length of $A$ and $B$, $M$ denotes the number of matching
positions between $A$ and $B$, and $\sigma$ denotes the number of distinct
characters occurring in both $A$ and $B$. Our new algorithm is faster than
Chowdhury et al.'s sparse algorithm when $\sigma = o(\log^2n \log\log n)$.
