It is definitely DP but after a trick identification.
Think something with the reverse and the original string.
When will the two on merging give the desired result.
Do we need all the terms in the reverse? think how to remove the redundancies.
The Terms needed will not be in the Longest common subsequence of the original and reverse string so remove the terms of LCS(original,reverse(original)) from reverse. You only need size.. so Subtract size.
Read more… (75 words)