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 :
4
Time Complexity :O(N)
Space Complexity : O(1)