This post is in reference to CodeForces Palindrome.

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 abcd are acd, bd, abcd, d, etc. The following are not: acb, da, abcde, dcba.

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

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.

Example input = abbca


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

1. LCPal of “a” is “a
2. LCPal of “b” is “b
3. LCPal of “ab” is “a” (taken from row above)
4. LCPal of “bb” is “bb” (take the match plus row/column above/beside, which is empty)
5. LCPal of “abb” is “bb” (taken from column beside)
6. LCPal of “bbc” is “bb” (taken from row above)
7. LCPal of “abbca” is “abba” (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:

Leave a Reply

Your email address will not be published. Required fields are marked *