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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int palindromeSubStrs ( string s ) { int dp [ s . size ( ) ] [ s . size ( ) ] ; int st , end , i , j , len ; map < string , bool > m ; for ( i = 0 ; i < s . size ( ) ; i ++ ) { dp [ i ] [ i ] = 1 ; m [ string ( s . begin ( ) + i , s . begin ( ) + i + 1 ) ] = 1 ; } for ( i = 0 ; i < s . size ( ) - 1 ; i ++ ) { if ( s [ i ] == s [ i + 1 ] ) { dp [ i ] [ i + 1 ] = 1 ; m [ string ( s . begin ( ) + i , s . begin ( ) + i + 2 ) ] = 1 ; } else { dp [ i ] [ i + 1 ] = 0 ; } } for ( len = 3 ; len <= s . size ( ) ; len ++ ) { for ( st = 0 ; st <= s . size ( ) - len ; st ++ ) { end = st + len - 1 ; if ( s [ st ] == s [ end ] && dp [ st + 1 ] [ end - 1 ] ) { dp [ st ] [ end ] = 1 ; m [ string ( s . begin ( ) + st , s . begin ( ) + end + 1 ) ] = 1 ; } else dp [ st ] [ end ] = 0 ; } } return m . size ( ) ; } int main ( ) { string s = " abaaa " ; cout << palindromeSubStrs ( s ) ; return 0 ; }