Minimize deletions in a Binary String to remove all subsequences of the form "0101" | Function to find minimum characters to be removed such that no subsequence of the form "0101" exists in the string ; Stores the partial sums ; Calculate partial sums ; Setting endpoints and deleting characters indices . ; Return count of deleted characters ; Driver Code
def findmin ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE maximum = 0 NEW_LINE incr = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT incr [ i + 1 ] = incr [ i ] NEW_LINE if ( s [ i ] == '0' ) : NEW_LINE INDENT incr [ i + 1 ] = incr [ i + 1 ] + 1 NEW_LINE DEDENT DEDENT for i in range ( 0 , n + 1 ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT maximum = max ( maximum , incr [ i ] + j - i + 1 - ( incr [ j + 1 ] - incr [ i ] ) + incr [ n ] - incr [ j + 1 ] ) NEW_LINE DEDENT DEDENT return n - maximum NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = "0110100110" NEW_LINE minimum = findmin ( S ) NEW_LINE print ( minimum ) NEW_LINE DEDENT