Crear palíndromo a partir de una cadena existente mediante la eliminación de caracteres

¿Cómo puedo determinar la longitud del palíndromo más largo que puede obtener de una palabra eliminando cero o más letras?

por ejemplo: amanQQQapl12345anacaZZZnalpaXXXna67890ma
El palíndromo más largo será de 21 dígitos.