Минимальное количество 0, которое нужно выбрать так, чтобы все 1 были смежными с ними

Дана двоичная строка str размера N , каждый символ которой равен либо '1', либо '0' . Задача состоит в том, чтобы выбрать минимальное количество 0 так, чтобы был выбран хотя бы один сосед для каждой '1' . Выведите количество выбранных 0’ с.

Примеры:

Input: str = “1001”
Output: 2
Explanation: ‘0’s can be selected from index 1 and index 2.  As a result, every ‘1’ has at least one neighbor present among the selected ‘0’s.

Input: str = “01010”
Output: 1
Explanation: ‘0’ at index 2 can be selected. As a result one neighbor for both the ‘1’ s are selected.

Input: str = “111”
Output: -1
Explanation: There is no ‘0’ in the given string. So there cannot be any neighbor of ‘1’ which is ‘0’.

Input: str = “110”
Output: -1
Explanation: There is no ‘0’ as neighbor for ‘1’ at first position.

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

• Начните перебирать строку с самого начала.
• Для каждой '1', если возможно, '0' выбирается из его окрестности.
• Теперь, если есть «0» до и после текущей «1» , всегда выбирайте соседа рядом с текущей «1» (потому что после этой «1» может быть больше «1», и это позволит выбрать минимальное число соседей).

Ниже приведена реализация вышеуказанного подхода:

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