Thursday, November 3, 2011

Find the Longest Sub-sequence that is a Palindrome within a String

Problem: Given a string, you can delete any characters, find the longest sub-sequence (the characters remained after your deletion) that is a palindrome.

Solution: For palindrome problem, one trick often used is to reverse the string. Here we first reverse the string, then find the longest common sub-sequence between the new string and the original one. It is a O(n^2) solution. Remember, there could be multiple longest common sub-sequences, some of them may not be palindrome, you need do some checks.

1 comment:

  1. Please could you explain (maybe an example??) where the LCS between S and reverse(S) is not a palindrome?

    ReplyDelete