Minimum flips required to keep all 1 s together in a Binary string | cpp implementation for Minimum number of flips required in a binary string such that all the 1 aTMs are together ; Length of the binary string ; Initial state of the dp dp [ 0 ] [ 0 ] will be 1 if the current bit is 1 and we have to flip it ; Initial state of the dp dp [ 0 ] [ 1 ] will be 1 if the current bit is 0 and we have to flip it ; dp [ i ] [ 0 ] = Flips required to make all previous bits zero + Flip required to make current bit zero ; dp [ i ] [ 1 ] = minimum flips required to make all previous states 0 or make previous states 1 satisfying the condition ; Minimum of answer and flips required to make all bits 0 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minFlip ( string a ) { int n = a . size ( ) ; vector < vector < int > > dp ( n + 1 , vector < int > ( 2 , 0 ) ) ; dp [ 0 ] [ 0 ] = ( a [ 0 ] == '1' ) ; dp [ 0 ] [ 1 ] = ( a [ 0 ] == '0' ) ; for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] + ( a [ i ] == '1' ) ; dp [ i ] [ 1 ] = min ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] ) + ( a [ i ] == '0' ) ; } int answer = INT_MAX ; for ( int i = 0 ; i < n ; i ++ ) { answer = min ( answer , dp [ i ] [ 1 ] + dp [ n - 1 ] [ 0 ] - dp [ i ] [ 0 ] ) ; } return min ( answer , dp [ n - 1 ] [ 0 ] ) ; } int main ( ) { string s = "1100111000101" ; cout << ( minFlip ( s ) ) ; }