Longest Palindromic Subsequence (dp solution)

Question

Among several dp solutions for this question, an easier solution is to reverse the given string and calculate LCS of the original and reversed string.

My question is will this approach yield correct result every time ?
For instance , a longest common subsequence of ACBAC and its reverse CABCA is ABC, which isn't a palindrome, but this still gives correct result due to other LCS being palindrome ACA, CAC.

So ,will this approach yield correct result every time even though a non-palindrome LCS may exist ?

The dp table ,if it helps.

    A C B A C
  0 0 0 0 0 0 
C 0 0 1 1 1 1 
A 0 1 1 1 2 2 
B 0 1 1 2 2 2 
C 0 1 2 2 2 3 
A 0 1 2 2 3 3  

Patterman

Answer 1

Yes, it's correct. This is implied by the following two facts, which together imply the needed equality.

1. The longest palindromic subsequence is at most as long as the longest common subsequence of the string and its reverse.

2. The longest palindromic subsequence is at least as long as the longest common subsequence of the string and its reverse.

Fact 1 is easy to prove: every palindromic subsequence of the string is of course a subsequence, and it's a subsequence of the string's reverse because S1 is a subsequence of S2 if and only if reverse(S1) is a subsequence of reverse(S2), and the reverse of a palindromic sequence is itself.

Fact 2 is subtler. We argue that, given an LCS of the string and its reverse, we can derive two palindromic subsequences whose mean length is equal to the LCS. It follows by an averaging argument that one or both is at least as long.

I'll illustrate the construction process with your example. Write down the common subsequence together with the indexes in the string.

A C B A C
1 2 3 4 5
A   B   C
 \  |  /
  A B C
5 4 3 2 1
C A B C A

We extract A (1, 4); B (3, 3); C (5, 2). We can derive one palindrome by taking the prefix where the first number does not exceed the second and mirroring it: 1, 3, 4 -> A B A. We derive the other in mirror fashion from the suffix where the second number does not exceed the first: 2, 3, 5 -> C B C.

 A  B  C
 1  3  5
.>>\ />>
   | |
 <</ \<<.
 4  3  2
 A  B  C

Observe that each letter of the subsequence is used exactly twice (one going and once coming, except the middle, which is used once in both palindromes), hence our observation about the mean holds.

Theriault

A very interesting take, ABC being sort of intersection of CBC and ABA. Another example BABBA; BBA, BBB, ABA. Much appreciated. – Patterman

What a great observation. – Lindemann