Count pairs of non | Python3 implementation of the approach ; Pre - processing function ; Get the size of the string ; Initially mark every position as false ; For the length ; Iterate for every index with length j ; If the length is less than 2 ; If characters are equal ; Check for equal ; Function to return the number of pairs ; Create the dp table initially ; Declare the left array ; Declare the right array ; Initially left [ 0 ] is 1 ; Count the number of palindrome pairs to the left ; Initially right most as 1 ; Count the number of palindrome pairs to the right ; Count the number of pairs ; Driver code
N = 100 NEW_LINE def pre_process ( dp , s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT dp [ i ] [ j ] = False NEW_LINE DEDENT DEDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT for i in range ( n - j + 1 ) : NEW_LINE INDENT if ( j <= 2 ) : NEW_LINE INDENT if ( s [ i ] == s [ i + j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ i + j - 1 ] = True NEW_LINE DEDENT DEDENT elif ( s [ i ] == s [ i + j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ i + j - 1 ] = dp [ i + 1 ] [ i + j - 2 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def countPairs ( s ) : NEW_LINE INDENT dp = [ [ False for i in range ( N ) ] for j in range ( N ) ] NEW_LINE pre_process ( dp , s ) NEW_LINE n = len ( s ) NEW_LINE left = [ 0 for i in range ( n ) ] NEW_LINE right = [ 0 for i in range ( n ) ] NEW_LINE left [ 0 ] = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i + 1 ) : NEW_LINE INDENT if ( dp [ j ] [ i ] == 1 ) : NEW_LINE INDENT left [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT right [ n - 1 ] = 1 NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT right [ i ] = right [ i + 1 ] NEW_LINE for j in range ( n - 1 , i - 1 , - 1 ) : NEW_LINE INDENT if ( dp [ i ] [ j ] == 1 ) : NEW_LINE INDENT right [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT ans += left [ i ] * right [ i + 1 ] NEW_LINE DEDENT return ans NEW_LINE DEDENT s = " abacaba " NEW_LINE print ( countPairs ( s ) ) NEW_LINE