Count All Palindromic Subsequence in a given String | Function return the total palindromic subsequence ; Create a 2D array to store the count of palindromic subsequence ; palindromic subsequence of length 1 ; check subsequence of length L is palindrome or not ; return total palindromic subsequence ; Driver program
def countPS ( str ) : NEW_LINE INDENT N = len ( str ) NEW_LINE cps = [ [ 0 for i in range ( N + 2 ) ] for j in range ( N + 2 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT cps [ i ] [ i ] = 1 NEW_LINE DEDENT for L in range ( 2 , N + 1 ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT k = L + i - 1 NEW_LINE if ( k < N ) : NEW_LINE INDENT if ( str [ i ] == str [ k ] ) : NEW_LINE INDENT cps [ i ] [ k ] = ( cps [ i ] [ k - 1 ] + cps [ i + 1 ] [ k ] + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT cps [ i ] [ k ] = ( cps [ i ] [ k - 1 ] + cps [ i + 1 ] [ k ] - cps [ i + 1 ] [ k - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT DEDENT return cps [ 0 ] [ N - 1 ] NEW_LINE DEDENT str = " abcb " NEW_LINE print ( " Total ▁ palindromic ▁ subsequence ▁ are ▁ : ▁ " , countPS ( str ) ) NEW_LINE