Maximum difference of zeros and ones in binary string | CPP Program to find the length of substring with maximum difference of zeroes and ones in binary string . ; Return true if there all 1 s ; Checking each index is 0 or not . ; Find the length of substring with maximum difference of zeroes and ones in binary string ; If string is over . ; If the state is already calculated . ; Returns length of substring which is having maximum difference of number of 0 s and number of 1 s ; If all 1 s return - 1. ; Else find the length . ; Driven Program
#include <bits/stdc++.h> NEW_LINE #define MAX  100 NEW_LINE using namespace std ; bool allones ( string s , int n ) { int co = 0 ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) co += ( s [ i ] == '1' ) ; return ( co == n ) ; } int findlength ( int arr [ ] , string s , int n , int ind , int st , int dp [ ] [ 3 ] ) { if ( ind >= n ) return 0 ; if ( dp [ ind ] [ st ] != -1 ) return dp [ ind ] [ st ] ; if ( st == 0 ) return dp [ ind ] [ st ] = max ( arr [ ind ] + findlength ( arr , s , n , ind + 1 , 1 , dp ) , findlength ( arr , s , n , ind + 1 , 0 , dp ) ) ; else return dp [ ind ] [ st ] = max ( arr [ ind ] + findlength ( arr , s , n , ind + 1 , 1 , dp ) , 0 ) ; } int maxLen ( string s , int n ) { if ( allones ( s , n ) ) return -1 ; int arr [ MAX ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) arr [ i ] = ( s [ i ] == '0' ? 1 : -1 ) ; int dp [ MAX ] [ 3 ] ; memset ( dp , -1 , sizeof dp ) ; return findlength ( arr , s , n , 0 , 0 , dp ) ; } int main ( ) { string s = "11000010001" ; int n = 11 ; cout << maxLen ( s , n ) << endl ; return 0 ; }