Count All Palindrome Sub | Returns total number of palindrome substring of length greater then equal to 2 ; creat empty 2 - D matrix that counts all palindrome substring . dp [ i ] [ j ] stores counts of palindromic substrings in st [ i . . j ] ; P [ i ] [ j ] = true if substring str [ i . . j ] is palindrome , else false ; palindrome of single length ; palindrome of length 2 ; Palindromes of length more than 2. This loop is similar to Matrix Chain Multiplication . We start with a gap of length 2 and fill DP table in a way that the gap between starting and ending indexes increase one by one by outer loop . ; Pick a starting point for the current gap ; Set ending point ; If current string is palindrome ; Add current palindrome substring ( + 1 ) and rest palindrome substring ( dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] ) remove common palindrome substrings ( - dp [ i + 1 ] [ j - 1 ] ) ; return total palindromic substrings ; Driver Code
def CountPS ( str , n ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( n ) ] for y in range ( n ) ] NEW_LINE P = [ [ False for x in range ( n ) ] for y in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT P [ i ] [ i ] = True NEW_LINE DEDENT for i in range ( n - 1 ) : NEW_LINE INDENT if ( str [ i ] == str [ i + 1 ] ) : NEW_LINE INDENT P [ i ] [ i + 1 ] = True NEW_LINE dp [ i ] [ i + 1 ] = 1 NEW_LINE DEDENT DEDENT for gap in range ( 2 , n ) : NEW_LINE INDENT for i in range ( n - gap ) : NEW_LINE INDENT j = gap + i NEW_LINE if ( str [ i ] == str [ j ] and P [ i + 1 ] [ j - 1 ] ) : NEW_LINE INDENT P [ i ] [ j ] = True NEW_LINE DEDENT if ( P [ i ] [ j ] == True ) : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] + 1 - dp [ i + 1 ] [ j - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] - dp [ i + 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ 0 ] [ n - 1 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str = " abaab " NEW_LINE n = len ( str ) NEW_LINE print ( CountPS ( str , n ) ) NEW_LINE DEDENT