Maximum difference of zeros and ones in binary string | Python 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
MAX = 100 NEW_LINE def allones ( s , n ) : NEW_LINE INDENT co = 0 NEW_LINE for i in s : NEW_LINE INDENT co += 1 if i == '1' else 0 NEW_LINE DEDENT return co == n NEW_LINE DEDENT def findlength ( arr , s , n , ind , st , dp ) : NEW_LINE INDENT if ind >= n : NEW_LINE INDENT return 0 NEW_LINE DEDENT if dp [ ind ] [ st ] != - 1 : NEW_LINE INDENT return dp [ ind ] [ st ] NEW_LINE DEDENT if not st : NEW_LINE INDENT dp [ ind ] [ st ] = max ( arr [ ind ] + findlength ( arr , s , n , ind + 1 , 1 , dp ) , ( findlength ( arr , s , n , ind + 1 , 0 , dp ) ) ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ ind ] [ st ] = max ( arr [ ind ] + findlength ( arr , s , n , ind + 1 , 1 , dp ) , 0 ) NEW_LINE DEDENT return dp [ ind ] [ st ] NEW_LINE DEDENT def maxLen ( s , n ) : NEW_LINE INDENT if allones ( s , n ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT arr = [ 0 ] * MAX NEW_LINE for i in range ( n ) : NEW_LINE INDENT arr [ i ] = 1 if s [ i ] == '0' else - 1 NEW_LINE DEDENT dp = [ [ - 1 ] * 3 for _ in range ( MAX ) ] NEW_LINE return findlength ( arr , s , n , 0 , 0 , dp ) NEW_LINE DEDENT s = "11000010001" NEW_LINE n = 11 NEW_LINE print ( maxLen ( s , n ) ) NEW_LINE