Minimum characters required to be removed to sort binary string in ascending order | 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 ; Given string str ; Function call
def minDeletion ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE DEDENT ' NEW_LINE INDENT firstIdx1 = - 1 NEW_LINE DEDENT ' NEW_LINE INDENT lastIdx0 = - 1 NEW_LINE DEDENT ' NEW_LINE INDENT for i in range ( 0 , n ) : NEW_LINE INDENT if ( str [ i ] == '1' ) : NEW_LINE INDENT firstIdx1 = i NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT ' NEW_LINE INDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( str [ i ] == '0' ) : NEW_LINE INDENT lastIdx0 = i NEW_LINE break NEW_LINE DEDENT DEDENT if ( firstIdx1 == - 1 or lastIdx0 == - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT count1 = 0 NEW_LINE count0 = 0 NEW_LINE for i in range ( 0 , lastIdx0 ) : NEW_LINE INDENT if ( str [ i ] == '1' ) : NEW_LINE INDENT count1 += 1 NEW_LINE DEDENT DEDENT for i in range ( firstIdx1 + 1 , n ) : NEW_LINE INDENT if ( str [ i ] == '1' ) : NEW_LINE INDENT count0 += 1 NEW_LINE DEDENT DEDENT return min ( count0 , count1 ) NEW_LINE DEDENT str = "1000101" NEW_LINE print ( minDeletion ( str ) ) NEW_LINE