Solução Palíndromo

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

O problema é uma DP em que o valor de $$dp(ini,fim)$$refere-se ao melhor palíndromo encontrado entre os índices $$ini$$ e $$fim$$ (inclusive) da $$string$$ inicial. Cada estado da DP retorna dois inteiros: $$qtd$$ (número de caracteres especiais) e $$tam$$ (tamanho do palíndromo). Seja $$word$$ a $$string$$ fornecida na entrada.

Se $$ini=fim$$, então o palíndromo terá tamanho 1, e só terá um caractere especial se $$ini$$ for uma das posições especiais. Se $$ini==fim-1$$, então, se as letras forem iguais temos um palíndromo de tamanho 2 e basta contarmos os caracteres especiais (no caso $$ini$$ ou $$fim$$) e, caso sejam diferente, o maior palíndromo tem tamanho 1 (uma das duas) e vai ter 1 caractere especial se uma das letras for especial.

Se $$word[ini]=word[fim]$$, então podemos usar ou não as letras $$word[ini]$$ e $$word[fim]$$ no nosso palíndromo resposta. Se usarmos adicionamos 2 ao tamanho de $$dp[ini+1][fim=1]$$ e o número de novos caracteres especiais (verificamos $$word[ini]$$ e $$word[fim]$$ e adicionamos 1 para cada um que seja especial). Se não as usarmos, vemos o melhor entre usar a letra esquerda ($$dp[ini][fim-1]$$) ou a direita ($$dp[ini+1][fim]$$).

Se $$word[ini] \neq word[fim]$$, então não podemos usar as duas letras e voltamos para a segunda opção do caso anterior. Segue o código par melhor entendimento:

https://gist.github.com/rogerioagjr/fc59d4db8a060af4cb3327471fff33b4