Solução por Leonardo Paes
Para resolver este problema, utilizaremos programação dinâmica.
Seja $$DP_{l, r}$$ a resposta para a substring $$S_{l, l + 1, \dots, r}$$.
Então, temos dois casos para considerar:
- A primeira letra da substring é deletada separadamente do resto, então $$DP_{l, r} = 1 + DP_{l+1, r}$$.
- A primeira letra da substring é deletada juntamente com alguma outra letra (ambas as letras devem ser iguais), então: $$DP_{l, r} = \min \limits_{l < i \le r, S_i = S_r} DP_{l + 1, i – 1} + DP_{i, r}$$.
Segue abaixo o código para melhor entendimento:
https://gist.github.com/Rockbet/6d42af2a137617650ebf0892684765c6