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]).

Answer 2

The longest palindrome in the word W is the longest common subsequence of W and its mirror.

You can compute it in O(n²) time and O(n) space where n is the length of W but if you know that you only need remove few characters to make a palindrome you can have better complexity.

Answer 3

A palidrome can have at most one odd counted letter i.e. the middle letter, and any number of even counted letters.

You can count the frequency of each letter. If it not all or nothing for each letter, add the count/2*2 for each letter and add one if any letter has an odd count.