Distinct palindromic sub | C # implementation of the approach ; Function to return the count of distinct palindromic sub - strings of the given string s ; To store the positions of palindromic sub - strings ; Map to store the sub - strings ; Sub - strings of length 1 are palindromes ; Store continuous palindromic sub - strings ; Store palindromes of size 2 ; If str [ i ... ( i + 1 ) ] is not a palindromic then set dp [ i , i + 1 ] = 0 ; Find palindromic sub - strings of length >= 3 ; End of palindromic substring ; If s [ start ] = = s [ end ] and dp [ start + 1 , end - 1 ] is already palindrome then s [ start ... . end ] is also a palindrome ; Set dp [ start , end ] = 1 ; Not a palindrome ; Return the count of distinct palindromes ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int palindromeSubStrs ( String s ) { int [ , ] dp = new int [ s . Length , s . Length ] ; int st , end , i , len ; Dictionary < String , Boolean > m = new Dictionary < String , Boolean > ( ) ; for ( i = 0 ; i < s . Length ; i ++ ) { dp [ i , i ] = 1 ; if ( ! m . ContainsKey ( s . Substring ( i , 1 ) ) ) m . Add ( s . Substring ( i , 1 ) , true ) ; } for ( i = 0 ; i < s . Length - 1 ; i ++ ) { if ( s [ i ] == s [ i + 1 ] ) { dp [ i , i + 1 ] = 1 ; if ( ! m . ContainsKey ( s . Substring ( i , 2 ) ) ) m . Add ( s . Substring ( i , 2 ) , true ) ; } else dp [ i , i + 1 ] = 0 ; } for ( len = 3 ; len <= s . Length ; len ++ ) { for ( st = 0 ; st <= s . Length - len ; st ++ ) { end = st + len - 1 ; if ( s [ st ] == s [ end ] && dp [ st + 1 , end - 1 ] == 1 ) { dp [ st , end ] = 1 ; m . Add ( s . Substring ( st , end + 1 - st ) , true ) ; } else dp [ st , end ] = 0 ; } } return m . Count ; } public static void Main ( String [ ] args ) { String s = " abaaa " ; Console . WriteLine ( palindromeSubStrs ( s ) ) ; } }