Дана строка, состоящая из прописных латинских букв. Можно удалять из этой строки все пары соседних одинаковых букв, включая пары, образовавшиеся после удаления других пар. Нужно заменить в заданной строке 0 или более букв так, чтобы после удаления всех пар строка стала пустой.
Входные данные:
Первая строка содержит одну строку четной длины от 2 до 200, состоящую из строчных букв латинского алфавита.
Выходные данные:
В первой строке вывести минимальное количество замен букв.
Пример:
| Входные данные |
Выходные данные |
| baddaacc |
1 |
Пояснение:
Можно заменить шестую букву на b, тогда процесс удаления будет выглядеть следующим образом: baddabcc -> baddab -> baab -> bb -> .