Подсчет количества замен в строке для получения чередующихся символов

220

19 декабря 2019, 03:10

У вас есть строка с символами 'Y' и 'B'.

Если они стоят по очереди, тогда это отлично и ничего менять не надо, но если они стоят например так: "YYB" тогда 1 букву нужно сменить на B, то есть что бы вышло "BYB". Нужно вывести сколько замен сделать что бы они стояли по очереди, то есть это должен быть greedy алгоритм.

Вот еще пример для наглядности:

BYB - 0 замен нужно,так как ничего менять не надо

YYBBB - 2, нужны 2 замены, то есть заменить 1 и 4 символ. Выйдет BYBYB.

Если у вас есть идеи то напишите сюда, буду очень признателен.

Answer 1

Всего у нас 2 варианта строки на выходе может быть — начинающаяся с Y и начинающаяся с B. Генерируем обе строки и проверяем для каждой из них сколько символов отличается от входной строки. Минимальное из двух значений возвращаем.