Number of palindromic subsequences of length k where k <= 3 | Python3 program to count number of subsequences of given length . ; Precompute the prefix and suffix array . ; Precompute the prefix 2D array ; Precompute the Suffix 2D array . ; Find the number of palindromic subsequence of length k ; If k is 1. ; If k is 2 ; Adding all the products of prefix array ; For k greater than 2. Adding all the products of value of prefix and suffix array . ; Driven Program
MAX = 100 NEW_LINE MAX_CHAR = 26 NEW_LINE def precompute ( s , n , l , r ) : NEW_LINE INDENT l [ ord ( s [ 0 ] ) - ord ( ' a ' ) ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( MAX_CHAR ) : NEW_LINE INDENT l [ j ] [ i ] += l [ j ] [ i - 1 ] NEW_LINE DEDENT l [ ord ( s [ i ] ) - ord ( ' a ' ) ] [ i ] += 1 NEW_LINE DEDENT r [ ord ( s [ n - 1 ] ) - ord ( ' a ' ) ] [ n - 1 ] = 1 NEW_LINE k = n - 2 NEW_LINE while ( k >= 0 ) : NEW_LINE INDENT for j in range ( MAX_CHAR ) : NEW_LINE INDENT r [ j ] [ k ] += r [ j ] [ k + 1 ] NEW_LINE DEDENT r [ ord ( s [ k ] ) - ord ( ' a ' ) ] [ k ] += 1 NEW_LINE k -= 1 NEW_LINE DEDENT DEDENT def countPalindromes ( k , n , l , r ) : NEW_LINE INDENT ans = 0 NEW_LINE if ( k == 1 ) : NEW_LINE INDENT for i in range ( MAX_CHAR ) : NEW_LINE INDENT ans += l [ i ] [ n - 1 ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if ( k == 2 ) : NEW_LINE INDENT for i in range ( MAX_CHAR ) : NEW_LINE INDENT ans += ( ( l [ i ] [ n - 1 ] * ( l [ i ] [ n - 1 ] - 1 ) ) / 2 ) NEW_LINE DEDENT return ans NEW_LINE DEDENT for i in range ( 1 , n - 1 ) : NEW_LINE INDENT for j in range ( MAX_CHAR ) : NEW_LINE INDENT ans += l [ j ] [ i - 1 ] * r [ j ] [ i + 1 ] NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT s = " aabab " NEW_LINE k = 2 NEW_LINE n = len ( s ) NEW_LINE l = [ [ 0 for x in range ( MAX ) ] for y in range ( MAX_CHAR ) ] NEW_LINE r = [ [ 0 for x in range ( MAX ) ] for y in range ( MAX_CHAR ) ] NEW_LINE precompute ( s , n , l , r ) NEW_LINE print ( countPalindromes ( k , n , l , r ) ) NEW_LINE