Минимальное количество замен подстроки «01» на «110», чтобы удалить ее полностью

Для заданной двоичной строки S задача состоит в том, чтобы найти минимальное количество повторяющихся замен подстроки «01» на строку «110» , чтобы в заданной строке S не существовало ни одной подстроки «01» .

Примеры:

Input: S = “01”
Output: 1
Explanation:
Below are the operations performed:
Operation 1: Choosing substring (0, 1) in the string “01” and replacing it with “110” modifies the given string to “110”.
After the above operations, the string S(= “110”) doesn’t contain any substring as “01”. Therefore, the total number of operation required is 1.

Input: S = “001”
Output:3
Explanation:
Below are the operations performed:
Operation 1: Choosing substring (1, 2) in the string “001” and replacing it with “110” modifies the given string to “0110”.
Operation 2: Choosing substring (0, 1) in the string “0110” and replacing it with “110” modifies the given string to “11010”.
Operation 3: Choosing substring (2, 3) in the string “11010” and replacing it with “110” modifies the given string to “111100”.
After the above operations, the string S(= “111100”) doesn’t contain any substring as “01”. Therefore, the total number of operation required is 3.

Подход: Данную задачу можно решить с помощью жадного подхода. Операция заключается в том, что всякий раз, когда найдена подстрока «01» , она заменяется на «110» , и теперь число «1» присутствует справа от этого «0», образуя подстроку «01» , которая принимает участие в изменении строки на «110» . Следовательно, идея состоит в том, чтобы пройти по строке с конца и всякий раз, когда встречается «0» , выполнять данную операцию до тех пор, пока количество единиц не будет представлено с правой стороны. Выполните следующие шаги, чтобы решить проблему:

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

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

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