Create palindrome from existing string by removing characters

Question

How do i determine the length of the longest palindrome you can get from a word by removing zero or more letters.

for eg : amanQQQapl12345anacaZZZnalpaXXXna67890ma
longest palindrome will be of 21 digits.

Answer 1

This can be solved by dynamic programming. Define d[i, j] as the length of longest palindrome in the original string.

If s[i] = s[j], d[i, j] = max(d[i+1, j-1] + 2, d[i, j-1], d[i+1, j]).

Otherwise d[i, j] = max(d[i, j-1], d[i+1, j]).