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

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

Примеры:

Input: S = “010001011” 
Output: 4 
Explanation: 
Removing the characters { S[2], S[3], S[4], S[6] } from the string S modifies the string S to “01111”. 
Therefore, the required output is 4.

Input: S = “011110000” 
Output: 0 
Explanation: 
All 1s in S already group together, therefore, the required output is 0.

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

• Переберите символы строки S слева направо и найдите индекс первого вхождения 1 s в данной строке, скажем, X .
• Пройдите строку справа налево и найдите индекс последнего вхождения 1 s в данной строке, скажем, Y .
• После выполнения вышеуказанных шагов выведите в качестве результата количество нулей между индексами X и Y.