Minimum characters required to be removed to sort binary string in ascending order | C ++ program for the above approach ; Function to find the minimum count of characters to be removed to make the string sorted in ascending order ; Length of given string ; Stores the first occurrence of '1' ; Stores the last occurrence of '0' ; Traverse the string to find the first occurrence of '1' ; Traverse the string to find the last occurrence of '0' ; Return 0 if the str have only one type of character ; Initialize count1 and count0 to count '1' s before lastIdx0 and '0' s after firstIdx1 ; Traverse the string to count0 ; Traverse the string to count1 ; Return the minimum of count0 and count1 ; Driver code ; Given string str ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minDeletion ( string str ) { int n = str . length ( ) ; int firstIdx1 = -1 ; int lastIdx0 = -1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '1' ) { firstIdx1 = i ; break ; } } for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( str [ i ] == '0' ) { lastIdx0 = i ; break ; } } if ( firstIdx1 == -1 lastIdx0 == -1 ) return 0 ; int count1 = 0 , count0 = 0 ; for ( int i = 0 ; i < lastIdx0 ; i ++ ) { if ( str [ i ] == '1' ) { count1 ++ ; } } for ( int i = firstIdx1 + 1 ; i < n ; i ++ ) { if ( str [ i ] == '1' ) { count0 ++ ; } } return min ( count0 , count1 ) ; } int main ( ) { string str = "1000101" ; cout << minDeletion ( str ) ; return 0 ; }