Ctrl K

Разбить длинные серии

Сложная
Дана двоичная строка bits и число flips. Можно не более flips раз выбрать любой символ строки и перевернуть его: 0 превратить в 1 или наоборот. Серия — это отрезок подряд идущих одинаковых символов. Переворачивайте символы так, чтобы самая длинная серия в строке стала как можно короче. Верните её длину.
Пример 1
bits="000000", flips=2 → 2

Переворачиваем символы с индексами 2 и 5: получится 001001, самая длинная серия — 2. Одной серии длины 1 двумя переворотами не добиться.

Пример 2
bits="1110111", flips=1 → 3

Один переворот может разбить только одну из двух серий 111, другая останется. Ответ 3.

Пример 3
bits="0110", flips=2 → 1
Ограничения
  • 1 ≤ len(bits) ≤ 1000
  • bits состоит только из 0 и 1
  • 0 ≤ flips ≤ len(bits)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВстреча видов мха СложнаяКрасота клумб на бюджете СложнаяВырезать блок ради подъёма ЛёгкаяОбщая медиана двух массивов СложнаяМинимум в сдвинутом массиве с повторами Сложная
загружаем Python…
Вход
bits="000000", flips=2
Ожидается
2

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