Module: Padrões em Programação Dinâmica - 2

Problem

Dada uma string que consiste em letras latinas maiúsculas. É possível remover desta string todos os pares de letras idênticas adjacentes, incluindo pares formados após a exclusão de outros pares. Você precisa substituir 0 ou mais letras na string fornecida para que, após excluir todos os pares, a string fique vazia.

Entrada:
A primeira linha contém uma string de comprimento par de 2 a 200, consistindo de letras latinas minúsculas.

Saída:
Na primeira linha, imprima o número mínimo de substituições de letras.

Exemplo:
 

Entrada	Saída
baddaacc	1

Explicação:
Você pode substituir a sexta letra por b, então o processo de remoção ficará assim: baddabcc -> baddab-> baab-> bb->  .