Longest subsequence of the form 0 * 1 * 0 * in a binary string | Returns length of the longest subsequence of the form 0 * 1 * 0 * ; Precomputing values in three arrays pre_count_0 [ i ] is going to store count of 0 s in prefix str [ 0. . i - 1 ] pre_count_1 [ i ] is going to store count of 1 s in prefix str [ 0. . i - 1 ] post_count_0 [ i ] is going to store count of 0 s in suffix str [ i - 1. . n - 1 ] ; string is made up of all 0 s or all 1 s ; Compute result using precomputed values ; Driver Code
def longestSubseq ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE pre_count_0 = [ 0 for i in range ( n + 2 ) ] NEW_LINE pre_count_1 = [ 0 for i in range ( n + 1 ) ] NEW_LINE post_count_0 = [ 0 for i in range ( n + 2 ) ] NEW_LINE pre_count_0 [ 0 ] = 0 NEW_LINE post_count_0 [ n + 1 ] = 0 NEW_LINE pre_count_1 [ 0 ] = 0 NEW_LINE for j in range ( 1 , n + 1 ) : NEW_LINE INDENT pre_count_0 [ j ] = pre_count_0 [ j - 1 ] NEW_LINE pre_count_1 [ j ] = pre_count_1 [ j - 1 ] NEW_LINE post_count_0 [ n - j + 1 ] = post_count_0 [ n - j + 2 ] NEW_LINE if ( s [ j - 1 ] == '0' ) : NEW_LINE INDENT pre_count_0 [ j ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT pre_count_1 [ j ] += 1 NEW_LINE DEDENT if ( s [ n - j ] == '0' ) : NEW_LINE INDENT post_count_0 [ n - j + 1 ] += 1 NEW_LINE DEDENT DEDENT if ( pre_count_0 [ n ] == n or pre_count_0 [ n ] == 0 ) : NEW_LINE INDENT return n NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( i , n + 1 , 1 ) : NEW_LINE INDENT ans = max ( pre_count_0 [ i - 1 ] + pre_count_1 [ j ] - pre_count_1 [ i - 1 ] + post_count_0 [ j + 1 ] , ans ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = "000011100000" NEW_LINE print ( longestSubseq ( s ) ) NEW_LINE DEDENT