Count All Palindrome Sub | C # program to find palindromic substrings of a string ; Returns total number of palindrome substring of length greater then equal to 2 ; create empty 2 - D matrix that counts all palindrome substring . dp [ i ] [ j ] stores counts of palindromic substrings in st [ i . . j ] ; P [ i ] [ j ] = true if substring str [ i . . j ] is palindrome , else false ; palindrome of single length ; palindrome of length 2 ; Palindromes of length more then 2. This loop is similar to Matrix Chain Multiplication . We start with a gap of length 2 and fill DP table in a way that gap between starting and ending indexes increases one by one by outer loop . ; Pick starting point for current gap ; Set ending point ; If current string is palindrome ; Add current palindrome substring ( + 1 ) and rest palindrome substring ( dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] ) remove common palindrome substrings ( - dp [ i + 1 ] [ j - 1 ] ) ; return total palindromic substrings ; Driver Code
using System ; class GFG { public static int CountPS ( char [ ] str , int n ) { int [ ] [ ] dp = RectangularArrays . ReturnRectangularIntArray ( n , n ) ; bool [ ] [ ] P = RectangularArrays . ReturnRectangularBoolArray ( n , n ) ; for ( int i = 0 ; i < n ; i ++ ) { P [ i ] [ i ] = true ; } for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( str [ i ] == str [ i + 1 ] ) { P [ i ] [ i + 1 ] = true ; dp [ i ] [ i + 1 ] = 1 ; } } for ( int gap = 2 ; gap < n ; gap ++ ) { for ( int i = 0 ; i < n - gap ; i ++ ) { int j = gap + i ; if ( str [ i ] == str [ j ] && P [ i + 1 ] [ j - 1 ] ) { P [ i ] [ j ] = true ; } if ( P [ i ] [ j ] == true ) { dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] + 1 - dp [ i + 1 ] [ j - 1 ] ; } else { dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] - dp [ i + 1 ] [ j - 1 ] ; } } } return dp [ 0 ] [ n - 1 ] ; } public static class RectangularArrays { public static int [ ] [ ] ReturnRectangularIntArray ( int size1 , int size2 ) { int [ ] [ ] newArray = new int [ size1 ] [ ] ; for ( int array1 = 0 ; array1 < size1 ; array1 ++ ) { newArray [ array1 ] = new int [ size2 ] ; } return newArray ; } public static bool [ ] [ ] ReturnRectangularBoolArray ( int size1 , int size2 ) { bool [ ] [ ] newArray = new bool [ size1 ] [ ] ; for ( int array1 = 0 ; array1 < size1 ; array1 ++ ) { newArray [ array1 ] = new bool [ size2 ] ; } return newArray ; } } public static void Main ( string [ ] args ) { string str = " abaab " ; Console . WriteLine ( CountPS ( str . ToCharArray ( ) , str . Length ) ) ; } }