Minimize deletions in a Binary String to remove all subsequences of the form "0101" | C ++ Program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findmin ( string s ) { int n = s . length ( ) ; int i , j , maximum = 0 ; int incr [ n + 1 ] = { 0 } ; for ( i = 0 ; i < n ; i ++ ) { incr [ i + 1 ] = incr [ i ] ; if ( s [ i ] == '0' ) { incr [ i + 1 ] ++ ; } } for ( i = 0 ; i < n ; i ++ ) { for ( j = i + 1 ; j < n ; j ++ ) { maximum = max ( maximum , incr [ i ] + j - i + 1 - ( incr [ j + 1 ] - incr [ i ] ) + incr [ n ] - incr [ j + 1 ] ) ; } } return n - maximum ; } int main ( ) { string S = "0110100110" ; int minimum = findmin ( S ) ; cout << minimum << ' ' ; }