Number of palindromic subsequences of length k where k <= 3 | Javascript 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 . ; Driver code
let MAX = 100 ; let MAX_CHAR = 26 ; function precompute ( s , n , l , r ) { l [ s [ 0 ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] [ 0 ] = 1 ; for ( let i = 1 ; i < n ; i ++ ) { for ( let j = 0 ; j < MAX_CHAR ; j ++ ) l [ j ] [ i ] += l [ j ] [ i - 1 ] ; l [ s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] [ i ] ++ ; } r [ s [ n - 1 ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] [ n - 1 ] = 1 ; for ( let i = n - 2 ; i >= 0 ; i -- ) { for ( let j = 0 ; j < MAX_CHAR ; j ++ ) r [ j ] [ i ] += r [ j ] [ i + 1 ] ; r [ s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] [ i ] ++ ; } } function countPalindromes ( k , n , l , r ) { let ans = 0 ; if ( k == 1 ) { for ( let i = 0 ; i < MAX_CHAR ; i ++ ) ans += l [ i ] [ n - 1 ] ; return ans ; } if ( k == 2 ) { for ( let i = 0 ; i < MAX_CHAR ; i ++ ) ans += ( ( l [ i ] [ n - 1 ] * ( l [ i ] [ n - 1 ] - 1 ) ) / 2 ) ; return ans ; } for ( let i = 1 ; i < n - 1 ; i ++ ) for ( let j = 0 ; j < MAX_CHAR ; j ++ ) ans += l [ j ] [ i - 1 ] * r [ j ] [ i + 1 ] ; return ans ; } let s = " " ; let k = 2 ; let n = s . length ; let l = new Array ( MAX_CHAR ) ; let r = new Array ( MAX_CHAR ) ; for ( let i = 0 ; i < MAX_CHAR ; i ++ ) { l [ i ] = new Array ( MAX ) ; r [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) { l [ i ] [ j ] = 0 ; r [ i ] [ j ] = 0 ; } } precompute ( s , n , l , r ) ; document . write ( countPalindromes ( k , n , l , r ) ) ;