Longest substring with count of 1 s more than 0 s | Function to find longest substring having count of 1 s more than count of 0 s . ; To store sum . ; To store first occurrence of each sum value . ; To store maximum length . ; To store current substring length . ; Add 1 if current character is 1 else subtract 1. ; If sum is positive , then maximum length substring is bin1 [ 0. . i ] ; If sum is negative , then maximum length substring is bin1 [ j + 1. . i ] , where sum of substring bin1 [ 0. . j ] is sum - 1. ; Make entry for this sum value in hash table if this value is not present . ; Driver code
def findLongestSub ( bin1 ) : NEW_LINE INDENT n = len ( bin1 ) NEW_LINE sum = 0 NEW_LINE prevSum = { i : 0 for i in range ( n ) } NEW_LINE maxlen = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( bin1 [ i ] == '1' ) : NEW_LINE INDENT sum += 1 NEW_LINE DEDENT else : NEW_LINE INDENT sum -= 1 NEW_LINE DEDENT if ( sum > 0 ) : NEW_LINE INDENT maxlen = i + 1 NEW_LINE DEDENT elif ( sum <= 0 ) : NEW_LINE INDENT if ( ( sum - 1 ) in prevSum ) : NEW_LINE INDENT currlen = i - prevSum [ sum - 1 ] NEW_LINE maxlen = max ( maxlen , currlen ) NEW_LINE DEDENT DEDENT if ( ( sum ) not in prevSum ) : NEW_LINE INDENT prevSum [ sum ] = i NEW_LINE DEDENT DEDENT return maxlen NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT bin1 = "1010" NEW_LINE print ( findLongestSub ( bin1 ) ) NEW_LINE DEDENT