Distinct palindromic sub | Java 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
import java . util . HashMap ; class GFG { static int palindromeSubStrs ( String s ) { int [ ] [ ] dp = new int [ s . length ( ) ] [ s . length ( ) ] ; int st , end , i , len ; HashMap < String , Boolean > m = new HashMap < > ( ) ; for ( i = 0 ; i < s . length ( ) ; i ++ ) { dp [ i ] [ i ] = 1 ; m . put ( s . substring ( i , i + 1 ) , true ) ; } for ( i = 0 ; i < s . length ( ) - 1 ; i ++ ) { if ( s . charAt ( i ) == s . charAt ( i + 1 ) ) { dp [ i ] [ i + 1 ] = 1 ; m . put ( s . substring ( i , 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 . charAt ( st ) == s . charAt ( end ) && dp [ st + 1 ] [ end - 1 ] == 1 ) { dp [ st ] [ end ] = 1 ; m . put ( s . substring ( st , end + 1 ) , true ) ; } else dp [ st ] [ end ] = 0 ; } } return m . size ( ) ; } public static void main ( String [ ] args ) { String s = " abaaa " ; System . out . println ( palindromeSubStrs ( s ) ) ; } }