Что такое флип строки и как его правильно реализовать?
Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества нулей (возможно ни одного), за которыми следует некоторое количество единиц (также возможно ни одного). Вы можете перевернуть любой символ строки, изменив его с 0 на 1 или с 1 на 0.
Входные данные: s - строка, символы которой могут быть только 0 или 1.
Необходимо вернуть минимальное количество переворотов, чтобы исходная строка монотонно возрастала.
Примеры:
1
2
s = "00110"
Output: 1
Пояснение: меняем последний символ и получаем “00111”
1
2
3
4
s = "010110"
Output: 2
s = "00011000"
Output: 2
Разбор
Итак, делаем проход по строке. На каждой итерации у нас есть 2 случая:
- Текущий символ это 1. В этом случае мы увеличим счетчик, подсчитывающий 1.
- Текущий символ это 0. Тут есть 2 варианта.
- Сохраняем 0, но переворачиваем все предыдущие 1.
- Переворачиваем 0 на 1 и обновляем счетчик, подсчитывающий перевороты.
- Теперь нам нужно определить какой вариант даст лучший результат: берем минимум от 2х счетчиков и обновляем счетчик, подсчитывающий перевороты.
- Детали реализации смотрите ниже.
Реализация