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

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

Примеры:

Input: S = “010”
Output: 2
Explanation:
Following are the order of flipping of substring of  at least K for the value of K as 2:

• Flip the substring S[0, 2] of length 3(>= K) modifies the string S to “101”.
• Flip the substring S[0, 1] of length 2(>= K) modifies the string S to “011”.
• Flip the substring S[1, 2] of length 2(>= K) modifies the string S to “000”.

For the value of K as 2(which is the maximum possible value) all the characters of the string can be made 0. Therefore, print 2.

Input: S = “00001111”
Output: 4

Подход: данная проблема может быть решена путем обхода заданной строки S , теперь, если в какой-либо точке соседние символы не совпадают, переверните одну подстроку LHS или RHS . Для этого возьмите максимальную длину LHS и RHS . Может быть несколько смежных мест, где символы не равны. Для каждой пары подстрок требуемый максимум будет разным. Теперь, чтобы изменить все символы на «0», возьмите минимум среди всех этих максимумов. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем , как N , которая хранит максимально возможное значение K.
• Переберите диапазон [0, N – 1), используя переменную i , и выполните следующие шаги:
  • Если значения s[i] и s[i + 1] не совпадают, обновите значение ans до минимума ans или максимума (i + 1) или (N – i – 1) .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

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