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.
Please could you explain (maybe an example??) where the LCS between S and reverse(S) is not a palindrome?
ReplyDelete