Number of ways to partition a string into two balanced subsequences | For maximum length of input string ; Declaring the DP table ; Function to calculate the number of valid assignments ; Return 1 if both subsequences are balanced ; Increment the count if it is an opening bracket ; Decrement the count if it a closing bracket ; Driver code ; Initial value for c_x and c_y is zero
MAX = 10 NEW_LINE F = [ [ [ - 1 for i in range ( MAX ) ] for j in range ( MAX ) ] for k in range ( MAX ) ] NEW_LINE def noOfAssignments ( S , n , i , c_x , c_y ) : NEW_LINE INDENT if F [ i ] [ c_x ] [ c_y ] != - 1 : NEW_LINE INDENT return F [ i ] [ c_x ] [ c_y ] NEW_LINE DEDENT if i == n : NEW_LINE INDENT F [ i ] [ c_x ] [ c_y ] = not c_x and not c_y NEW_LINE return F [ i ] [ c_x ] [ c_y ] NEW_LINE DEDENT if S [ i ] == ' ( ' : NEW_LINE INDENT F [ i ] [ c_x ] [ c_y ] = noOfAssignments ( S , n , i + 1 , c_x + 1 , c_y ) + noOfAssignments ( S , n , i + 1 , c_x , c_y + 1 ) NEW_LINE return F [ i ] [ c_x ] [ c_y ] NEW_LINE DEDENT F [ i ] [ c_x ] [ c_y ] = 0 NEW_LINE if c_x : NEW_LINE INDENT F [ i ] [ c_x ] [ c_y ] += noOfAssignments ( S , n , i + 1 , c_x - 1 , c_y ) NEW_LINE DEDENT if c_y : NEW_LINE INDENT F [ i ] [ c_x ] [ c_y ] += noOfAssignments ( S , n , i + 1 , c_x , c_y - 1 ) NEW_LINE DEDENT return F [ i ] [ c_x ] [ c_y ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " ( ( ) ) " NEW_LINE n = len ( S ) NEW_LINE print ( noOfAssignments ( S , n , 0 , 0 , 0 ) ) NEW_LINE DEDENT