Сокращение строки - Конкурс по программированию . Требуется решение

У меня есть вопрос, который просит нас сократить строку следующим образом.

На вход подается строка, содержащая только A, B или C. Вывод должен быть длиной сокращенной строки

Строка может быть сокращена по следующим правилам

Если любые 2 разные буквы являются соседними, эти две буквы могут быть заменить третьей буквой.

Например, ABA -> CA -> B . Поэтому окончательный ответ - 1 (длина сокращенной строки)

Например, ABCCCCCCC

Это не становится CCCCCCC, так как оно может быть сокращено альтернативным способом

ABCCCCCCC->AACCCCCC->ABCCCCC->AACCCC->ABCCC-. >AACC->ABC->AA

так как здесь длина 2 < (длина CCCCCCC)

Как решить эту задачу?

Спасибо большое!

Чтобы прояснить ситуацию: в вопросе говорится, что нужна минимальная длина сокращенной строки. Поэтому во втором примере возможны 2 решения: одно CCCCCCCCCC, а другое AA. Поэтому ответом будет 2, так как длина AA равна 2, что меньше длины CCCCCCCCCC = 8.