text: Total number of odd length palindrome sub | Java implementation of above approach ; Function to find the total palindromic odd length sub - sequences ; dp array to store the number of palindromic subsequences for 0 to i - 1 and j + 1 to n - 1 ; We will start with the largest distance between i and j ; For each len , we fix our i ; For this i we will find our j ; Base cases ; If the characters are equal then look for out of bound index ; We have only 1 way that is to just pick these characters ; If the characters are not equal ; Subtract it as we have counted it twice ; We have just 1 palindrome sequence of length 1 ; Else total ways would be sum of dp [ i - 1 ] [ i + 1 ] , that is number of palindrome sub - sequences from 1 to i - 1 + number of palindrome sub - sequences from i + 1 to n - 1 ; Driver code
code: import java . util . * ; class GFG { static void solve ( char [ ] s ) { int n = s . length ; int [ ] [ ] dp = new int [ n ] [ n ] ; for ( int len = n - 1 ; len >= 0 ; -- len ) { for ( int i = 0 ; i + len < n ; ++ i ) { int j = i + len ; if ( i == 0 && j == n - 1 ) { if ( s [ i ] == s [ j ] ) dp [ i ] [ j ] = 2 ; else if ( s [ i ] != s [ j ] ) dp [ i ] [ j ] = 1 ; } else { if ( s [ i ] == s [ j ] ) { if ( i - 1 >= 0 ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j ] ; } if ( j + 1 <= n - 1 ) { dp [ i ] [ j ] += dp [ i ] [ j + 1 ] ; } if ( i - 1 < 0 j + 1 >= n ) { dp [ i ] [ j ] += 1 ; } } else if ( s [ i ] != s [ j ] ) { if ( i - 1 >= 0 ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j ] ; } if ( j + 1 <= n - 1 ) { dp [ i ] [ j ] += dp [ i ] [ j + 1 ] ; } if ( i - 1 >= 0 && j + 1 <= n - 1 ) { dp [ i ] [ j ] -= dp [ i - 1 ] [ j + 1 ] ; } } } } } Vector < Integer > ways = new Vector < > ( ) ; for ( int i = 0 ; i < n ; ++ i ) { if ( i == 0 i == n - 1 ) { ways . add ( 1 ) ; } else { int total = dp [ i - 1 ] [ i + 1 ] ; ways . add ( total ) ; } } for ( int i = 0 ; i < ways . size ( ) ; ++ i ) { System . out . print ( ways . get ( i ) + " ▁ " ) ; } } public static void main ( String [ ] args ) { char [ ] s = " xyxyx " . toCharArray ( ) ; solve ( s ) ; } }