Tutorialspoint.dev

Count All Palindrome Sub-Strings in a String | Set 1

Given a string, the task is to count all palindrome substring in a given string. Length of palindrome substring is greater then 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]

   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 Subprolems. Since the problem has overlapping sub-problems, we can solve it efficiently using Dynamic Programming. Below is a Dynamic Programming based solution.



C/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 then equal to 2
int CountPS(char str[], int n)
{
    // creat empty 2-D matrix that counts all palindrome
    // substring. dp[i][j] stores counts of palindromic
    // substrings in st[i..j]
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
  
    // 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 lenght
    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 palinrome substring (dp[i][j-1] + dp[i+1][j])
            // remove common palinrome 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 program
int main()
{
    char str[] = "abaab";
    int n = strlen(str);
    cout << CountPS(str, n) << endl;
    return 0;
}

Java

// Java program to find palindromic substrings of a string
  
public class GFG 
{
    // Returns total number of palindrome substring of
    // length greater then equal to 2
    static int CountPS(char str[], int n)
    {
        // creat 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 lenght
        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 then 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 palinrome substring (dp[i][j-1] + dp[i+1][j])
                // remove common palinrome 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 Method
    public static void main(String[] args)
    {
        String str = "abaab";
        System.out.println(CountPS(str.toCharArray(), str.length()));
    }
}

Python 3

# Python 3 program to find palindromic 
# substrings of a string
  
# Returns total number of palindrome 
# substring of length greater then 
# equal to 2
def CountPS(str, n):
  
    # creat 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 lenght
    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 palinrome substring (dp[i][j-1] + 
            # dp[i+1][j]) remove common palinrome 
            # 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
if __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 string 
using System;
  
class GFG
{
// Returns total number of 
// palindrome substring of 
// length greater then equal to 2 
public static int CountPS(char[] str, 
                          int n)
{
    // creat 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 lenght 
    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 then 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 palinrome substring 
            // (dp[i][j-1] + dp[i+1][j]) remove common
            // palinrome 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 then equal to 2 
function CountPS($str, $n
    // creat 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 lenght 
    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 then 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 palinrome substring (dp[i][j-1] + 
            // dp[i+1][j]) remove common palinrome
            // 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
?>


Output:

3

Time complexity: O(n2)
Auxiliary Space: O(n2)

Count All Palindrome Sub-Strings in a String | Set 2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

1 Comments

load comments

Subscribe to Our Newsletter