Number of balanced bracket subsequence of length 2 and 4 | Python 3 implementation of above approach ; Taking the frequency suffix sum of the number of 2 's present  after every index ; Storing the count of subsequence ; Subsequence of length 2 ; Subsequence of length 4 of type 1 1 2 2 ; Subsequence of length 4 of type 1 2 1 2 ; Driver Code
def countWays ( a , n ) : NEW_LINE INDENT suff = [ 0 ] * n NEW_LINE if ( a [ n - 1 ] == 2 ) : NEW_LINE INDENT suff [ n - 1 ] = 1 NEW_LINE DEDENT for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( a [ i ] == 2 ) : NEW_LINE INDENT suff [ i ] = suff [ i + 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT suff [ i ] = suff [ i + 1 ] NEW_LINE DEDENT DEDENT ss = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( a [ i ] == 1 ) : NEW_LINE INDENT ss += suff [ i ] NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT if ( a [ i ] == 1 and a [ j ] == 1 and suff [ j ] >= 2 ) : NEW_LINE INDENT ss += ( suff [ j ] ) * ( suff [ j ] - 1 ) // 2 NEW_LINE DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT if ( a [ i ] == 1 and a [ j ] == 1 and ( suff [ i ] - suff [ j ] ) >= 1 and suff [ j ] >= 1 ) : NEW_LINE INDENT ss += ( suff [ i ] - suff [ j ] ) * suff [ j ] NEW_LINE DEDENT DEDENT DEDENT print ( ss ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 2 , 1 , 1 , 2 , 2 ] NEW_LINE n = 6 NEW_LINE countWays ( a , n ) NEW_LINE DEDENT