Given a string S. The task is to count the non-overlapping pairs of palindromic sub-strings S1 and S2 such that the strings should be S1[L1…R1] and S2[L2…R2] where 0 ? L1 ? R1 < L2 ? R2 < N. The task is to count the number of pairs of the non-overlapping palindromic sub-strings.
Examples:
Input: s = “aaa”
Output: 5
All possible pairs are (s[0], s[1]), (s[0], s[2]),
(s[0], s[1, 2]), (s[1], s[2]) and (s[0, 1], s[2])
Input: s = “abacaba”
Output: 36
Approach: We can use Dynamic Programming to solve the above problem. We can initially create the DP table which stores if substring[i….j] is palindrome or not. We maintain a boolean dp[n][n] that is filled in a bottom-up manner. The value of dp[i][j] is true if the substring is a palindrome, otherwise false. To calculate dp[i][j], we first check the value of dp[i+1][j-1], if the value is true and s[i] is same as s[j], then we make dp[i][j] true. Otherwise, the value of dp[i][j] is made false. The following steps can be followed thereafter to get the number of pairs.
- Create a left[] array, where left[i] stores the count of the number of palindromes to the left on the index i including i.
- Create a right[] array, where right[i] stores the count of the number of palindromes to the right on the index i including i.
- Iterate from 0 to length-1 and add left[i]*right[i+1]. The summation of it for every index will be the required number of pairs.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define N 100 // Pre-processing function void pre_process( bool dp[N][N], string s) { // Get the size of the string int n = s.size(); // Initially mark every // position as false for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) dp[i][j] = false ; } // For the length for ( int j = 1; j <= n; j++) { // Iterate for every index with // length j for ( int i = 0; i <= n - j; i++) { // If the length is less than 2 if (j <= 2) { // If characters are equal if (s[i] == s[i + j - 1]) dp[i][i + j - 1] = true ; } // Check for equal else if (s[i] == s[i + j - 1]) dp[i][i + j - 1] = dp[i + 1][i + j - 2]; } } } // Function to return the number of pairs int countPairs(string s) { // Create the dp table initially bool dp[N][N]; pre_process(dp, s); int n = s.length(); // Declare the left array int left[n]; memset (left, 0, sizeof left); // Declare the right array int right[n]; memset (right, 0, sizeof right); // Initially left[0] is 1 left[0] = 1; // Count the number of palindrome // pairs to the left for ( int i = 1; i < n; i++) { for ( int j = 0; j <= i; j++) { if (dp[j][i] == 1) left[i]++; } } // Initially right most as 1 right[n - 1] = 1; // Count the number of palindrome // pairs to the right 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; // Count the number of pairs for ( int i = 0; i < n - 1; i++) ans += left[i] * right[i + 1]; return ans; } // Driver code int main() { string s = "abacaba" ; cout << countPairs(s); return 0; } |
Java
// Java implementation of the approach class GFG { static int N = 100 ; // Pre-processing function static void pre_process( boolean dp[][], char [] s) { // Get the size of the string int n = s.length; // Initially mark every // position as false for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { dp[i][j] = false ; } } // For the length for ( int j = 1 ; j <= n; j++) { // Iterate for every index with // length j for ( int i = 0 ; i <= n - j; i++) { // If the length is less than 2 if (j <= 2 ) { // If characters are equal if (s[i] == s[i + j - 1 ]) { dp[i][i + j - 1 ] = true ; } } // Check for equal else if (s[i] == s[i + j - 1 ]) { dp[i][i + j - 1 ] = dp[i + 1 ][i + j - 2 ]; } } } } // Function to return the number of pairs static int countPairs(String s) { // Create the dp table initially boolean dp[][] = new boolean [N][N]; pre_process(dp, s.toCharArray()); int n = s.length(); // Declare the left array int left[] = new int [n]; // Declare the right array int right[] = new int [n]; // Initially left[0] is 1 left[ 0 ] = 1 ; // Count the number of palindrome // pairs to the left for ( int i = 1 ; i < n; i++) { for ( int j = 0 ; j <= i; j++) { if (dp[j][i] == true ) { left[i]++; } } } // Initially right most as 1 right[n - 1 ] = 1 ; // Count the number of palindrome // pairs to the right 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] == true ) { right[i]++; } } } int ans = 0 ; // Count the number of pairs for ( int i = 0 ; i < n - 1 ; i++) { ans += left[i] * right[i + 1 ]; } return ans; } // Driver code public static void main(String[] args) { String s = "abacaba" ; System.out.println(countPairs(s)); } } // This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach N = 100 # Pre-processing function def pre_process(dp, s): # Get the size of the string n = len (s) # Initially mark every # position as false for i in range (n): for j in range (n): dp[i][j] = False # For the length for j in range ( 1 , n + 1 ): # Iterate for every index with # length j for i in range (n - j + 1 ): # If the length is less than 2 if (j < = 2 ): # If characters are equal if (s[i] = = s[i + j - 1 ]): dp[i][i + j - 1 ] = True # Check for equal elif (s[i] = = s[i + j - 1 ]): dp[i][i + j - 1 ] = dp[i + 1 ][i + j - 2 ] # Function to return the number of pairs def countPairs(s): # Create the dp table initially dp = [[ False for i in range (N)] for j in range (N)] pre_process(dp, s) n = len (s) # Declare the left array left = [ 0 for i in range (n)] # Declare the right array right = [ 0 for i in range (n)] # Initially left[0] is 1 left[ 0 ] = 1 # Count the number of palindrome # pairs to the left for i in range ( 1 , n): for j in range (i + 1 ): if (dp[j][i] = = 1 ): left[i] + = 1 # Initially right most as 1 right[n - 1 ] = 1 # Count the number of palindrome # pairs to the right for i in range (n - 2 , - 1 , - 1 ): right[i] = right[i + 1 ] for j in range (n - 1 , i - 1 , - 1 ): if (dp[i][j] = = 1 ): right[i] + = 1 ans = 0 # Count the number of pairs for i in range (n - 1 ): ans + = left[i] * right[i + 1 ] return ans # Driver code s = "abacaba" print (countPairs(s)) # This code is contributed by mohit kumar |
PHP
<?php // PHP implementation of the approach $N = 100; // Pre-processing function function pre_process( $dp , $s ) { // Get the size of the string $n = strlen ( $s ); // Initially mark every // position as false for ( $i = 0; $i < $n ; $i ++) { for ( $j = 0; $j < $n ; $j ++) $dp [ $i ][ $j ] = false; } // For the length for ( $j = 1; $j <= $n ; $j ++) { // Iterate for every index with // length j for ( $i = 0; $i <= $n - $j ; $i ++) { // If the length is less than 2 if ( $j <= 2) { // If characters are equal if ( $s [ $i ] == $s [ $i + $j - 1]) $dp [ $i ][ $i + $j - 1] = true; } // Check for equal else if ( $s [ $i ] == $s [ $i + $j - 1]) $dp [ $i ][ $i + $j - 1] = $dp [ $i + 1][ $i + $j - 2]; } } return $dp ; } // Function to return the number of pairs function countPairs( $s ) { // Create the dp table initially $dp = array ( array ()); $dp = pre_process( $dp , $s ); $n = strlen ( $s ); // Declare the left array $left = array_fill (0, $n , 0); // Declare the right array $right = array_fill (0, $n , 0); // Initially left[0] is 1 $left [0] = 1; // Count the number of palindrome // pairs to the left for ( $i = 1; $i < $n ; $i ++) { for ( $j = 0; $j <= $i ; $j ++) { if ( $dp [ $j ][ $i ] == 1) $left [ $i ]++; } } // Initially right most as 1 $right [ $n - 1] = 1; // Count the number of palindrome // pairs to the right 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; // Count the number of pairs for ( $i = 0; $i < $n - 1; $i ++) $ans += $left [ $i ] * $right [ $i + 1]; return $ans ; } // Driver code $s = "abacaba" ; echo countPairs( $s ); // This code is contributed by Ryuga ?> |
C#
// C# implementation of the approach using System; class GFG { static int N = 100; // Pre-processing function static void pre_process( bool [,]dp, char [] s) { // Get the size of the string int n = s.Length; // Initially mark every // position as false for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { dp[i,j] = false ; } } // For the length for ( int j = 1; j <= n; j++) { // Iterate for every index with // length j for ( int i = 0; i <= n - j; i++) { // If the length is less than 2 if (j <= 2) { // If characters are equal if (s[i] == s[i + j - 1]) { dp[i,i + j - 1] = true ; } } // Check for equal else if (s[i] == s[i + j - 1]) { dp[i,i + j - 1] = dp[i + 1,i + j - 2]; } } } } // Function to return the number of pairs static int countPairs(String s) { // Create the dp table initially bool [,]dp = new bool [N,N]; pre_process(dp, s.ToCharArray()); int n = s.Length; // Declare the left array int []left = new int [n]; // Declare the right array int []right = new int [n]; // Initially left[0] is 1 left[0] = 1; // Count the number of palindrome // pairs to the left for ( int i = 1; i < n; i++) { for ( int j = 0; j <= i; j++) { if (dp[j,i] == true ) { left[i]++; } } } // Initially right most as 1 right[n - 1] = 1; // Count the number of palindrome // pairs to the right 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] == true ) { right[i]++; } } } int ans = 0; // Count the number of pairs for ( int i = 0; i < n - 1; i++) { ans += left[i] * right[i + 1]; } return ans; } // Driver code public static void Main(String[] args) { String s = "abacaba" ; Console.Write(countPairs(s)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // javascript implementation of the approach var N = 100; // Pre-processing function function pre_process( dp, s) { // Get the size of the string var n = s.length; // Initially mark every // position as false for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { dp[i][j] = false ; } } // For the length for (j = 1; j <= n; j++) { // Iterate for every index with // length j for (i = 0; i <= n - j; i++) { // If the length is less than 2 if (j <= 2) { // If characters are equal if (s[i] == s[i + j - 1]) { dp[i][i + j - 1] = true ; } } // Check for equal else if (s[i] == s[i + j - 1]) { dp[i][i + j - 1] = dp[i + 1][i + j - 2]; } } } } // Function to return the number of pairs function countPairs(s) { // Create the dp table initially var dp = Array(N).fill().map(()=>Array(N).fill( false )); pre_process(dp, s); var n = s.length; // Declare the left array var left = Array(n).fill(0); // Declare the right array var right = Array(n).fill(0); // Initially left[0] is 1 left[0] = 1; // Count the number of palindrome // pairs to the left for (i = 1; i < n; i++) { for (j = 0; j <= i; j++) { if (dp[j][i] == true ) { left[i]++; } } } // Initially right most as 1 right[n - 1] = 1; // Count the number of palindrome // pairs to the right for (i = n - 2; i >= 0; i--) { right[i] = right[i + 1]; for (j = n - 1; j >= i; j--) { if (dp[i][j] == true ) { right[i]++; } } } var ans = 0; // Count the number of pairs for (i = 0; i < n - 1; i++) { ans += left[i] * right[i + 1]; } return ans; } // Driver code var s = "abacaba" ; document.write(countPairs(s)); // This code is contributed by todaysgaurav </script> |
36
Time Complexity: O(N*N), as we are using nested loops for traversing N*N times. Where N is the length of the string.
Auxiliary Space: O(N*N), as we are using extra space for the dp matrix.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!