Number of palindromic subsequences of length k where k <= 3 | C # 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
using System ; class GFG { static int MAX = 100 ; static int MAX_CHAR = 26 ; static void precompute ( string s , int n , int [ , ] l , int [ , ] r ) { l [ s [ 0 ] - ' a ' , 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < MAX_CHAR ; j ++ ) l [ j , i ] += l [ j , i - 1 ] ; l [ s [ i ] - ' a ' , i ] ++ ; } r [ s [ n - 1 ] - ' a ' , n - 1 ] = 1 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { for ( int j = 0 ; j < MAX_CHAR ; j ++ ) r [ j , i ] += r [ j , i + 1 ] ; r [ s [ i ] - ' a ' , i ] ++ ; } } static int countPalindromes ( int k , int n , int [ , ] l , int [ , ] r ) { int ans = 0 ; if ( k == 1 ) { for ( int i = 0 ; i < MAX_CHAR ; i ++ ) ans += l [ i , n - 1 ] ; return ans ; } if ( k == 2 ) { for ( int i = 0 ; i < MAX_CHAR ; i ++ ) ans += ( ( l [ i , n - 1 ] * ( l [ i , n - 1 ] - 1 ) ) / 2 ) ; return ans ; } for ( int i = 1 ; i < n - 1 ; i ++ ) for ( int j = 0 ; j < MAX_CHAR ; j ++ ) ans += l [ j , i - 1 ] * r [ j , i + 1 ] ; return ans ; } public static void Main ( ) { string s = " aabab " ; int k = 2 ; int n = s . Length ; int [ , ] l = new int [ MAX_CHAR , MAX ] ; int [ , ] r = new int [ MAX_CHAR , MAX ] ; precompute ( s , n , l , r ) ; Console . Write ( countPalindromes ( k , n , l , r ) ) ; } }