Минимальное количество альтернативных подпоследовательностей, которые необходимо удалить, чтобы очистить двоичную строку.

Для заданной двоичной строки S , состоящей из N символов, задача состоит в том, чтобы напечатать минимальное количество операций, необходимых для удаления всех символов из заданной строки S путем удаления одного символа или удаления любой подпоследовательности альтернативных символов в каждой операции.

Примеры:

Input: S = “010101”
Output: 1
Explanation:
Below are the operations performed:
Operation 1: Consider the subsequence S[0, 5] i.e., “010101” as it contains alternating characters. Therefore, removing this modifies the string to “”.
Hence, the total number of operation required is 1.

Input: S = “00011”
Output: 3

Подход: Данную проблему можно решить, перебирая строку один раз и отслеживая максимальное количество оставшихся нулей и единиц . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, ans для хранения максимального количества нулей и единиц , которые еще осталось удалить, переменную cnt0 для подсчета количества нулей и переменную cnt1 для подсчета количества единиц.
• Пройдите заданную строку S с самого начала и выполните следующие шаги:
  • Если текущий символ равен 0 , то увеличьте значение cnt0 на 1 и уменьшите значение cnt1 на 1 , если оно больше 0 .
  • Если текущий символ равен 1 , увеличьте значение cnt1 на 1 и уменьшите значение cnt0 на 1 , если оно больше 0 .
  • Обновите значение ans до максимального числа ans , cnt1 и cnt0 .
• После выполнения вышеуказанных шагов выведите значение ans как минимальное количество операций, необходимых для удаления всех символов.

Ниже приведена реализация подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)