Minimum count of 0s to be removed from given Binary string to make all 1s occurs consecutively

Given a Binary String S of length N which consists of only 0 and 1, the task is to remove minimum number of 0’s from the string such that all 1’s form a contiguous subsegment. Return numbers of 0’s which are removed, if the string is already having all 1’s in contiguous format return -1.

Examples:

Input : 010001011
Output : 4
Explanation : 
By removing underlined 4 0's from the string 010001011 we can make a string 01111 which has 
all 1's as a contiguous subsegment.

Input : 011110000 
Output : -1

Approach :

Find the index of first occurrence of 1 in given string
Find the index of last occurrence of 1 in given string
Count number of 0’s present in between these two indices, print count if greater than 0 else print -1.

Implementation in C++:

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;

//Function to count number of 0's to be 
//removed from given string to make all 
//1's contiguous
void makeContiguous (string S, int N)
{
    //to store the first and last occurance
    //of 1 in given string
    int first_occurance,last_occurance;
    
    //for loop to find first occurance
    for(int x=0; x<N; x++)
    {
        if(S[x]=='1')
        {
            first_occurance=x;
            break;
        }
    }
    
    //for loop to last first occurance
    for(int x=N-1; x>=0; x--)
    {
        if(S[x]=='1')
        {
            last_occurance=x;
            break;
        }
    }
    
    //to count number of 0's 
    int count=0;
    
    for(int x=first_occurance; x<=last_occurance; x++)
    {
        if(S[x]=='0')
        count++;
    }
    
    if(count!=0)
    cout<< count;
    else
    cout<<-1;
   
}

// Driver Code
int main()
{
    // Given string, S
    string S = "010001011";
 
    // Store the size of S
    int N = S.size();
 
    // Function Call
    makeContiguous(S, N);
 
    return 0;
}

Output :

Time Complexity :O(N)
Space Complexity : O(1)