Count of ways to empty given String by recursively removing all adjacent duplicates | Python3 implementation for the above approach ; Define the dp table globally ; Recursive function to calculate the dp values for range [ L , R ] ; The range is odd length ; The state is already calculated ; If the length is 2 ; Total answer for this state ; Variable to store the current answer . ; Remove characters s [ l ] and s [ i ] . ; Initialize all the states of dp to - 1 memset ( dp , - 1 , sizeof ( dp ) ) ; ; Calculate all Combinations ; Driver Code
import numpy as np NEW_LINE dp = np . zeros ( ( 505 , 505 ) ) ; NEW_LINE choose = np . zeros ( ( 502 , 502 ) ) ; NEW_LINE def calc ( l , r , s ) : NEW_LINE INDENT if ( abs ( r - l ) % 2 == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( l > r ) : NEW_LINE INDENT dp [ l ] [ r ] = 1 ; NEW_LINE return dp [ l ] [ r ] NEW_LINE DEDENT if ( dp [ l ] [ r ] != - 1 ) : NEW_LINE INDENT return dp [ l ] [ r ] ; NEW_LINE DEDENT if ( ( r - l ) == 1 ) : NEW_LINE INDENT if ( s [ l ] == s [ r ] ) : NEW_LINE INDENT dp [ l ] [ r ] = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ l ] [ r ] = 0 ; NEW_LINE DEDENT return dp [ l ] [ r ] ; NEW_LINE DEDENT ans = 0 ; NEW_LINE for k in range ( l + 1 , r + 1 , 2 ) : NEW_LINE INDENT temp = 1 ; NEW_LINE if ( s [ l ] == s [ k ] ) : NEW_LINE INDENT temp = calc ( l + 1 , k - 1 , s ) * calc ( k + 1 , r , s ) * choose [ ( r - l + 1 ) // 2 ] [ ( r - k ) // 2 ] ; NEW_LINE ans += temp ; NEW_LINE DEDENT DEDENT dp [ l ] [ r ] = ans ; NEW_LINE return dp [ l ] [ r ] NEW_LINE DEDENT def waysToClearString ( S ) : NEW_LINE INDENT for i in range ( 505 ) : NEW_LINE INDENT for j in range ( 505 ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT n = len ( S ) ; NEW_LINE choose [ 0 ] [ 0 ] = 1 ; NEW_LINE for i in range ( 1 , ( n // 2 ) + 1 ) : NEW_LINE INDENT choose [ i ] [ 0 ] = 1 ; NEW_LINE for j in range ( 1 , i + 1 ) : NEW_LINE INDENT choose [ i ] [ j ] = choose [ i - 1 ] [ j ] + choose [ i - 1 ] [ j - 1 ] ; NEW_LINE DEDENT DEDENT return calc ( 0 , n - 1 , S ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " aabccb " ; NEW_LINE print ( waysToClearString ( S ) ) ; NEW_LINE DEDENT