Модуль: Паттерны в динамическом программировании - 2


Задача

3 /5


Удаление пар

Задача

Дана строка, состоящая из прописных латинских букв. Можно удалять из этой строки все пары соседних одинаковых букв, включая пары, образовавшиеся после удаления других пар. Нужно заменить в заданной строке 0 или более букв так, чтобы после удаления всех пар строка стала пустой.

Входные данные:
Первая строка содержит одну строку четной длины от 2 до 200, состоящую из строчных букв латинского алфавита.

Выходные данные:
В первой строке вывести минимальное количество замен букв.

Пример:
 
Входные данные Выходные данные
baddaacc 1

Пояснение:
Можно заменить шестую букву на b, тогда процесс удаления будет выглядеть следующим образом: baddabcc -> baddab -> baab -> bb ->  .
 


time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Mingw-w641
Комментарий учителя