Count pairs of non | C ++ implementation of the approach ; Pre - processing function ; Get the size of the string ; Initially mark every position as false ; For the length ; Iterate for every index with length j ; If the length is less than 2 ; If characters are equal ; Check for equal ; Function to return the number of pairs ; Create the dp table initially ; Declare the left array ; Declare the right array ; Initially left [ 0 ] is 1 ; Count the number of palindrome pairs to the left ; Initially right most as 1 ; Count the number of palindrome pairs to the right ; Count the number of pairs ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100 NEW_LINE void pre_process ( bool dp [ N ] [ N ] , string s ) { int n = s . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) dp [ i ] [ j ] = false ; } for ( int j = 1 ; j <= n ; j ++ ) { for ( int i = 0 ; i <= n - j ; i ++ ) { if ( j <= 2 ) { if ( s [ i ] == s [ i + j - 1 ] ) dp [ i ] [ i + j - 1 ] = true ; } else if ( s [ i ] == s [ i + j - 1 ] ) dp [ i ] [ i + j - 1 ] = dp [ i + 1 ] [ i + j - 2 ] ; } } } int countPairs ( string s ) { bool dp [ N ] [ N ] ; pre_process ( dp , s ) ; int n = s . length ( ) ; int left [ n ] ; memset ( left , 0 , sizeof left ) ; int right [ n ] ; memset ( right , 0 , sizeof right ) ; left [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j <= i ; j ++ ) { if ( dp [ j ] [ i ] == 1 ) left [ i ] ++ ; } } right [ n - 1 ] = 1 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { right [ i ] = right [ i + 1 ] ; for ( int j = n - 1 ; j >= i ; j -- ) { if ( dp [ i ] [ j ] == 1 ) right [ i ] ++ ; } } int ans = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) ans += left [ i ] * right [ i + 1 ] ; return ans ; } int main ( ) { string s = " abacaba " ; cout << countPairs ( s ) ; return 0 ; }