Count pairs of non | PHP 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
< ? php $ N = 100 ; function pre_process ( $ dp , $ s ) { $ n = strlen ( $ s ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ dp [ $ i ] [ $ j ] = false ; } for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { for ( $ 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 ] ; } } return $ dp ; } function countPairs ( $ s ) { $ dp = array ( array ( ) ) ; $ dp = pre_process ( $ dp , $ s ) ; $ n = strlen ( $ s ) ; $ left = array_fill ( 0 , $ n , 0 ) ; $ right = array_fill ( 0 , $ n , 0 ) ; $ left [ 0 ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j <= $ i ; $ j ++ ) { if ( $ dp [ $ j ] [ $ i ] == 1 ) $ left [ $ i ] ++ ; } } $ right [ $ n - 1 ] = 1 ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { $ right [ $ i ] = $ right [ $ i + 1 ] ; for ( $ j = $ n - 1 ; $ j >= $ i ; $ j -- ) { if ( $ dp [ $ i ] [ $ j ] == 1 ) $ right [ $ i ] ++ ; } } $ ans = 0 ; for ( $ i = 0 ; $ i < $ n - 1 ; $ i ++ ) $ ans += $ left [ $ i ] * $ right [ $ i + 1 ] ; return $ ans ; } $ s = " abacaba " ; echo countPairs ( $ s ) ; ? >