Ctrl K

Прореживание повторов

Средняя
Дана строка text. Ход устроен так: выбираете позицию i, у которой и слева, и справа есть буквы, равные text[i]. Затем стираете ближайшую такую букву слева от i и ближайшую справа. Сама буква на позиции i остаётся. Ходы можно делать сколько угодно раз. Верните наименьшую длину строки, которой можно добиться.
Пример 1
text="xxxyxx" → 2

Букв x пять: выбираем среднюю из них и стираем соседние слева и справа, потом ещё раз — остаётся одна x. С единственной y ничего не сделать. Итого 2.

Пример 2
text="mmnn" → 4

Ни у одной буквы нет копий и слева, и справа от другой такой же, поэтому строка не меняется.

Пример 3
text="aaaa" → 2

Выбираем вторую a и стираем первую и третью — остаются две a, больше ходов нет.

Ограничения
  • 1 ≤ len(text) ≤ 2·10⁵
  • text состоит из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПодсказка к угадыванию кода СредняяСимволы, сгруппированные по частоте СредняяСамые частые запросы СредняяБез одинаковых соседей СредняяСводка заходов по доменам Средняя
загружаем Python…
Вход
text="xxxyxx"
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 50 тестов на сервере, включая скрытые.