Given a string, the task is to count all palindrome sub string in a given string. Length of palindrome sub string is greater than or equal to 2.
Examples:
Input : str = "abaab" Output: 3 Explanation : All palindrome substring are : "aba" , "aa" , "baab" Input : str = "abbaeae" Output: 4 Explanation : All palindrome substring are : "bb" , "abba" ,"aea","eae"
We have discussed a similar problem below.
Find all distinct palindromic sub-strings of a given string
The above problem can be recursively defined.
Initial Values : i = 0, j = n-1;
Given string 'str'
CountPS(i, j)
// If length of string is 2 then we
// check both character are same or not
If (j == i+1)
return str[i] == str[j]
// this condition shows that in recursion if i crosses
// j then it will be a invalid substring or
// if i==j that means only one character is remaining
// and we require substring of length 2
//in both the conditions we need to return 0
Else if(i == j || i > j) return 0;
Else If str[i..j] is PALINDROME
// increment count by 1 and check for
// rest palindromic substring (i, j-1), (i+1, j)
// remove common palindrome substring (i+1, j-1)
return countPS(i+1, j) + countPS(i, j-1) + 1 -
countPS(i+1, j-1);
Else // if NOT PALINDROME
// We check for rest palindromic substrings (i, j-1)
// and (i+1, j)
// remove common palindrome substring (i+1 , j-1)
return countPS(i+1, j) + countPS(i, j-1) -
countPS(i+1 , j-1);
If we draw recursion tree of above recursive solution, we can observe overlapping Subproblems. Since the problem has overlapping sub-problems, we can solve it efficiently using Dynamic Programming.
Below is a Dynamic Programming based solution.
C++
// C++ program to find palindromic substrings of a string#include <bits/stdc++.h>using namespace std;// Returns total number of palindrome substring of// length greater than equal to 2int CountPS(char str[], int n){ //to store the count of palindrome subarrays int ans=0; // P[i][j] = true if substring str[i..j] is palindrome, // else false bool P[n][n]; memset(P, false, sizeof(P)); // palindrome of single length for (int i = 0; i < n; i++){ P[i][i] = true; } // Palindromes of length more than or equal to 2. We start with // a gap of length 1 and fill the DP table in a way that // gap between starting and ending indexes increases one // by one by outer loop. for (int gap = 2; gap <=n; gap++) { // Pick starting point for current gap for (int i = 0; i <= n-gap; i++) { // Set ending point int j = gap + i-1; // check If current string is palindrome of length 2 if(i==j-1){ P[i][j]=(str[i]==str[j]); }else { //check if the current substring is palindrome of length more than 2 //if characters at index i,j are equal check for string in between them //from i+1 to j-1 if it is palindrome or not P[i][j]=(str[i]==str[j] && P[i+1][j-1]); } //if substring from index i to j is palindrome increase the count if(P[i][j]){ ans++; } } } // return total palindromic substrings return ans;}// Driver codeint main(){ char str[] = "abaab"; int n = strlen(str); cout << CountPS(str, n) << endl; return 0;} |
Java
// Java program to find palindromic substrings of a stringpublic class GFG { // Returns total number of palindrome substring of // length greater than equal to 2 static int CountPS(char str[], int n) { // create empty 2-D matrix that counts all // palindrome substring. dp[i][j] stores counts of // palindromic substrings in st[i..j] int dp[][] = new int[n][n]; // P[i][j] = true if substring str[i..j] is // palindrome, else false boolean P[][] = new boolean[n][n]; // palindrome of single length for (int i = 0; i < n; i++) P[i][i] = true; // palindrome of length 2 for (int i = 0; i < n - 1; i++) { if (str[i] == str[i + 1]) { P[i][i + 1] = true; dp[i][i + 1] = 1; } } // Palindromes of length more than 2. This loop is // similar to Matrix Chain Multiplication. We start // with a gap of length 2 and fill the DP table in a // way that gap between starting and ending indexes // increases one by one by outer loop. for (int gap = 2; gap < n; gap++) { // Pick starting point for current gap for (int i = 0; i < n - gap; i++) { // Set ending point int j = gap + i; // If current string is palindrome if (str[i] == str[j] && P[i + 1][j - 1]) P[i][j] = true; // Add current palindrome substring ( + 1) // and rest palindrome substring (dp[i][j-1] // + dp[i+1][j]) remove common palindrome // substrings (- dp[i+1][j-1]) if (P[i][j] == true) dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1 - dp[i + 1][j - 1]; else dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]; } } // return total palindromic substrings return dp[0][n - 1]; } // Driver code public static void main(String[] args) { String str = "abaab"; System.out.println( CountPS(str.toCharArray(), str.length())); }} |
Python3
# Python3 program to find palindromic# substrings of a string# Returns total number of palindrome# substring of length greater than# equal to 2def CountPS(str, n): # create empty 2-D matrix that counts # all palindrome substring. dp[i][j] # stores counts of palindromic # substrings in st[i..j] dp = [[0 for x in range(n)] for y in range(n)] # P[i][j] = true if substring str[i..j] # is palindrome, else false P = [[False for x in range(n)] for y in range(n)] # palindrome of single length for i in range(n): P[i][i] = True # palindrome of length 2 for i in range(n - 1): if (str[i] == str[i + 1]): P[i][i + 1] = True dp[i][i + 1] = 1 # Palindromes of length more than 2. This # loop is similar to Matrix Chain Multiplication. # We start with a gap of length 2 and fill DP # table in a way that the gap between starting and # ending indexes increase one by one by # outer loop. for gap in range(2, n): # Pick a starting point for the current gap for i in range(n - gap): # Set ending point j = gap + i # If current string is palindrome if (str[i] == str[j] and P[i + 1][j - 1]): P[i][j] = True # Add current palindrome substring ( + 1) # and rest palindrome substring (dp[i][j-1] + # dp[i+1][j]) remove common palindrome # substrings (- dp[i+1][j-1]) if (P[i][j] == True): dp[i][j] = (dp[i][j - 1] + dp[i + 1][j] + 1 - dp[i + 1][j - 1]) else: dp[i][j] = (dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]) # return total palindromic substrings return dp[0][n - 1]# Driver Codeif __name__ == "__main__": str = "abaab" n = len(str) print(CountPS(str, n))# This code is contributed by ita_c |
C#
// C# program to find palindromic// substrings of a stringusing System;class GFG { // Returns total number of // palindrome substring of // length greater than equal to 2 public static int CountPS(char[] str, int n) { // create empty 2-D matrix that counts // all palindrome substring. dp[i][j] // stores counts of palindromic // substrings in st[i..j] int[][] dp = RectangularArrays.ReturnRectangularIntArray( n, n); // P[i][j] = true if substring str[i..j] // is palindrome, else false bool[][] P = RectangularArrays.ReturnRectangularBoolArray( n, n); // palindrome of single length for (int i = 0; i < n; i++) { P[i][i] = true; } // palindrome of length 2 for (int i = 0; i < n - 1; i++) { if (str[i] == str[i + 1]) { P[i][i + 1] = true; dp[i][i + 1] = 1; } } // Palindromes of length more than 2. // This loop is similar to Matrix Chain // Multiplication. We start with a gap // of length 2 and fill DP table in a // way that gap between starting and // ending indexes increases one by one // by outer loop. for (int gap = 2; gap < n; gap++) { // Pick starting point for current gap for (int i = 0; i < n - gap; i++) { // Set ending point int j = gap + i; // If current string is palindrome if (str[i] == str[j] && P[i + 1][j - 1]) { P[i][j] = true; } // Add current palindrome substring // ( + 1) and rest palindrome substring // (dp[i][j-1] + dp[i+1][j]) remove common // palindrome substrings (- dp[i+1][j-1]) if (P[i][j] == true) { dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1 - dp[i + 1][j - 1]; } else { dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]; } } } // return total palindromic substrings return dp[0][n - 1]; } public static class RectangularArrays { public static int[][] ReturnRectangularIntArray( int size1, int size2) { int[][] newArray = new int[size1][]; for (int array1 = 0; array1 < size1; array1++) { newArray[array1] = new int[size2]; } return newArray; } public static bool[][] ReturnRectangularBoolArray( int size1, int size2) { bool[][] newArray = new bool[size1][]; for (int array1 = 0; array1 < size1; array1++) { newArray[array1] = new bool[size2]; } return newArray; } } // Driver Code public static void Main(string[] args) { string str = "abaab"; Console.WriteLine( CountPS(str.ToCharArray(), str.Length)); }}// This code is contributed by Shrikant13 |
PHP
<?php// PHP program to find palindromic substrings// of a string // Returns total number of palindrome // substring of length greater than equal to 2 function CountPS($str, $n) { // create empty 2-D matrix that counts // all palindrome substring. dp[i][j] // stores counts of palindromic // substrings in st[i..j] $dp = array(array()); for ($i = 0; $i < $n; $i++) for($j = 0; $j < $n; $j++) $dp[$i][$j] = 0; // P[i][j] = true if substring str[i..j] // is palindrome, else false $P = array(array()); for ($i = 0; $i < $n; $i++) for($j = 0; $j < $n; $j++) $P[$i][$j] = false; // palindrome of single length for ($i= 0; $i< $n; $i++) $P[$i][$i] = true; // palindrome of length 2 for ($i = 0; $i < $n - 1; $i++) { if ($str[$i] == $str[$i + 1]) { $P[$i][$i + 1] = true; $dp[$i][$i + 1] = 1; } } // Palindromes of length more than 2. This // loop is similar to Matrix Chain Multiplication. // We start with a gap of length 2 and fill DP // table in a way that gap between starting and // ending indexes increases one by one by // outer loop. for ($gap = 2; $gap < $n; $gap++) { // Pick starting point for current gap for ($i = 0; $i < $n - $gap; $i++) { // Set ending point $j = $gap + $i; // If current string is palindrome if ($str[$i] == $str[$j] && $P[$i + 1][$j - 1]) $P[$i][$j] = true; // Add current palindrome substring (+ 1) // and rest palindrome substring (dp[i][j-1] + // dp[i+1][j]) remove common palindrome // substrings (- dp[i+1][j-1]) if ($P[$i][$j] == true) $dp[$i][$j] = $dp[$i][$j - 1] + $dp[$i + 1][$j] + 1 - $dp[$i + 1][$j - 1]; else $dp[$i][$j] = $dp[$i][$j - 1] + $dp[$i + 1][$j] - $dp[$i + 1][$j - 1]; } } // return total palindromic substrings return $dp[0][$n - 1]; } // Driver Code $str = "abaab"; $n = strlen($str); echo CountPS($str, $n);// This code is contributed by Ryuga?> |
Javascript
<script>// Javascript program to find palindromic substrings of a string // Returns total number of palindrome substring of // length greater than equal to 2 function CountPS(str,n) { // create empty 2-D matrix that counts all // palindrome substring. dp[i][j] stores counts of // palindromic substrings in st[i..j] let dp=new Array(n); // P[i][j] = true if substring str[i..j] is // palindrome, else false let P=new Array(n); for(let i=0;i<n;i++) { dp[i]=new Array(n); P[i]=new Array(n); for(let j=0;j<n;j++) { dp[i][j]=0; P[i][j]=false; } } // palindrome of single length for (let i = 0; i < n; i++) P[i][i] = true; // palindrome of length 2 for (let i = 0; i < n - 1; i++) { if (str[i] == str[i + 1]) { P[i][i + 1] = true; dp[i][i + 1] = 1; } } // Palindromes of length more than 2. This loop is // similar to Matrix Chain Multiplication. We start // with a gap of length 2 and fill the DP table in a // way that gap between starting and ending indexes // increases one by one by outer loop. for (let gap = 2; gap < n; gap++) { // Pick starting point for current gap for (let i = 0; i < n - gap; i++) { // Set ending point let j = gap + i; // If current string is palindrome if (str[i] == str[j] && P[i + 1][j - 1]) P[i][j] = true; // Add current palindrome substring ( + 1) // and rest palindrome substring (dp[i][j-1] // + dp[i+1][j]) remove common palindrome // substrings (- dp[i+1][j-1]) if (P[i][j] == true) dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1 - dp[i + 1][j - 1]; else dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]; } } // return total palindromic substrings return dp[0][n - 1]; } // Driver code let str = "abaab"; document.write( CountPS(str.split(""), str.length)); // This code is contributed by avanitrachhadiya2155 </script> |
Output
3
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Method 2: This approach uses Top Down DP i.e memoized version of recursion.
Recursive soln: 1. Here base condition comes out to be i>j if we hit this condition, return 1. 2. We check for each and every i and j, if the characters are equal, if that is not the case, return 0. 3. Call the is_palindrome function again with incremented i and decremented j. 4. Check this for all values of i and j by applying 2 for loops.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;int dp[1001][1001]; // 2D matrixbool isPal(string s, int i, int j){ // Base condition if (i > j) return 1; // check if the recursive tree // for given i, j // has already been executed if (dp[i][j] != -1) return dp[i][j]; // If first and last characters of // substring are unequal if (s[i] != s[j]) return dp[i][j] = 0; // memoization return dp[i][j] = isPal(s, i + 1, j - 1); }int countSubstrings(string s){ memset(dp, -1, sizeof(dp)); int n = s.length(); int count = 0; // 2 for loops are required to check for // all the palindromes in the string. for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Increment count for every palindrome if (isPal(s, i, j)) count++; } } // return total palindromic substrings return count;}// Driver codeint main(){ string s = "abbaeae"; cout << countSubstrings(s); //"bb" , "abba" ,"aea", "eae" are // the 4 palindromic substrings. // This code is contributed by Bhavneet Singh return 0;} |
Java
import java.util.*;public class Main{ static int dp[][] = new int[1001][1001]; // 2D matrix public static int isPal(String s, int i, int j) { // Base condition if (i > j) return 1; // check if the recursive tree // for given i, j // has already been executed if (dp[i][j] != -1) return dp[i][j]; // If first and last characters of // substring are unequal if (s.charAt(i) != s.charAt(j)) return dp[i][j] = 0; // memoization return dp[i][j] = isPal(s, i + 1, j - 1); } public static int countSubstrings(String s) { for (int[] row: dp) { Arrays.fill(row, -1); } int n = s.length(); int count = 0; // 2 for loops are required to check for // all the palindromes in the string. for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Increment count for every palindrome if (isPal(s, i, j) != 0) count++; } } // return total palindromic substrings return count; } public static void main(String[] args) { String s = "abbaeae"; System.out.println(countSubstrings(s)); }}// This code is contributed by divyeshrabadiya07 |
Python3
# 2D matrixdp = [[-1 for i in range(1001)] for j in range(1001)]def isPal(s, i, j): # Base condition if (i > j): return 1 # Check if the recursive tree # for given i, j # has already been executed if (dp[i][j] != -1): return dp[i][j] # If first and last characters of # substring are unequal if (s[i] != s[j]): dp[i][j] = 0 return dp[i][j] # Memoization dp[i][j] = isPal(s, i + 1, j - 1) return dp[i][j]def countSubstrings(s): n = len(s) count = 0 # 2 for loops are required to check for # all the palindromes in the string. for i in range(n): for j in range(i + 1, n): # Increment count for every palindrome if (isPal(s, i, j)): count += 1 # Return total palindromic substrings return count# Driver codes = "abbaeae"print(countSubstrings(s))# This code is contributed by rag2127 |
C#
using System;class GFG{// 2D matrixstatic int[,] dp = new int[1001, 1001]; static int isPal(string s, int i, int j){ // Base condition if (i > j) return 1; // Check if the recursive tree // for given i, j // has already been executed if (dp[i, j] != -1) return dp[i, j]; // If first and last characters of // substring are unequal if (s[i] != s[j]) return dp[i, j] = 0; // Memoization return dp[i, j] = isPal(s, i + 1, j - 1); } static int countSubstrings(string s){ for(int i = 0; i < 1001; i++) { for(int j = 0; j < 1001; j++) { dp[i, j] = -1; } } int n = s.Length; int count = 0; // 2 for loops are required to check for // all the palindromes in the string. for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { // Increment count for every palindrome if (isPal(s, i, j) != 0) count++; } } // Return total palindromic substrings return count;}// Driver Code static void Main(){ string s = "abbaeae"; Console.WriteLine(countSubstrings(s));}}// This code is contributed by divyesh072019 |
Javascript
<script> var dp = Array(1001).fill().map(()=>Array(1001).fill(-1)); // 2D matrix function isPal( s , i , j) { // Base condition if (i > j) return 1; // check if the recursive tree // for given i, j // has already been executed if (dp[i][j] != -1) return dp[i][j]; // If first and last characters of // substring are unequal if (s.charAt(i) != s.charAt(j)) return dp[i][j] = 0; // memoization return dp[i][j] = isPal(s, i + 1, j - 1); } function countSubstrings( s) { var n = s.length; var count = 0; // 2 for loops are required to check for // all the palindromes in the string. for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Increment count for every palindrome if (isPal(s, i, j) != 0) count++; } } // return total palindromic substrings return count; } // Driver code var s = "abbaeae"; document.write(countSubstrings(s)); // This code is contributed by Rajput-Ji</script> |
Output
4
Time Complexity: O(n3)
Auxiliary Space: O(n2)
Count All Palindrome Sub-Strings in a String | Set 2
This article is contributed by Nishant_Singh(Pintu). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
