The question is: given a string, can you find the longest palindrome sub-sequence?

N.B. A sub-sequence of a string is what remains after removing any characters you’d like, keeping the order unchanged. Sub-sequences of are , , , , etc. The following are not: , , , .

The solution uses dynamic programming on a 2D vector, with input string along both the top and side. The number of cells is .

Grid[row][col] means “longest sub-sequence within input sub-string [col…row]”. The grid is calculated from top to bottom, each row from right to left.

Explanations:

N.B. LCPal is Longest Common Sub-Sequence Palindrome

1. LCPal of “” is “”

2. LCPal of “” is “”

3. LCPal of “” is “” (taken from row above)

4. LCPal of “” is “” (take the match plus row/column above/beside, which is empty)

5. LCPal of “” is “” (taken from column beside)

6. LCPal of “” is “” (taken from row above)

7. LCPal of “” is “” (take the match plus row/column above/beside), and that’s the final answer

And an implementation note: because each row only requires the previous, I don’t keep all rows in memory — just two.

My solution is in git and below:

Continue reading