A string is a palindrome when it reads the same backward as forward and a substring is a contiguous sequence of characters within the string. In this article, we shall discuss multiple approaches to find the number of palindromic substrings in a given string like:

• Brute force approach (two pointer approach)
• Recursive approach
• Dynamic programming approach
• Modifed Manacher’s algoritm

Let us discuss all of them one by one in this article.

Examples:
Input : str = "bcbbc"
Output: 8
Explaination: palindromic substrings:
'b','c','b','b','c','bcb','cbbc','bb'

Input : str = "eaaebeb"
Output: 11
Explaination: palindromic substrings:
'e','a','a','e','b','e','b','eaae','aa','beb','ebe'

Brute Force approach

In the brute force solution, we take each substring one by one by two pointer approach and check if it is a palindrome or not.

Implementation

Implementation of Brute Force approach in C++:

#include <iostream>
#include<string>
using namespace std;

bool isPalindromic(string s, int i, int j)
{   
    if (i > j)
        return 1;
 
    if (s[i] != s[j])
        return  0;
 
    return isPalindromic(s, i + 1, j - 1);
}

int main() {
    string str;
    cin>>str;
    
    int count =0;
    
    for(int i=0;i<str.length();i++){
        for(int j=i;j<str.length();j++){
            if(isPalindromic(str,i,j)){
                count++;
            }    
        }
    }
    cout<<count;
}

For an input string of length n, there would be a total of O(n^2) substrings. Checking each substring to see if it’s a palindrome or not would take linear time as we would have to look at each character of the substring exactly once if it is a palindrome. Thus checking each substring takes O(n) time.

Therefore, to check all the substrings and return the total palindromic substrings in the original input string the brute force method would take O(n^3) time.

• Time Complexity: O(N^3)
• Space Complexity: O(1)

Let us now discuss if there is a better solution to this problem.

Recursive method:

If i and j are the starting and the ending index of the string then,

Algorithm:

1. If i>j then no such substring is possible therefore we return 0;
2. If i==j then there is only a single character in the substring and as we know every character is a palindromic substring therefore we return 1;
3. we have a substring from i to j and now we check if the substring is palindrome or not.
4. If the substring from i to j is a palindrome then we increment the number of palindromic substrings by 1 and recursively check for the substrings (i, j-1) and (i+1, j) and remove the common palindrome substring (i+1,j-1).
5. If the substring from i to j is not a palindrome then we recursively check for rest palindromic substrings (i, j-1) and (i+1, j) and remove common palindrome substring (i+1 , j-1).

Implementation:

Implementation of our Recursive method in C++:

#include <iostream>
#include<string>
using namespace std;

bool isPalindromic(string s, int i, int j)
{   
    if (i > j)
        return 1;
 
    if (s[i] != s[j])
        return  0;
 
    return isPalindromic(s, i + 1, j - 1);
}

int PalindromicSubstrings(int i, int j,string str){
   if(i>j) return 0;

   if(i==j) return 1;
   
   if(isPalindromic(str,i,j)) return PalindromicSubstrings(i+1,j,str)+ PalindromicSubstrings(i,j-1,str)+1-PalindromicSubstrings(i+1, j-1,str);

   else return  PalindromicSubstrings(i+1,j,str)+ PalindromicSubstrings(i,j-1,str)-PalindromicSubstrings(i+1, j-1,str);

}   

int main() {

    string str;
    cin>>str;
    cout<<PalindromicSubstrings(0,str.length()-1,str);
}

For this recursive approach we observe that in the recursion tree there are overlapping subproblems and therefore, we can solve it efficiently using Dynamic Programming.

Bottom-Up Dynamic Programming Approach

To implement the bottom up dynamic programming approach, we consider two 2-D arrays dp and p of size n X n ,where n is the string length.
dp[i][j] stores the count of palindromic substrings from index i to j and p [i][j] boolean value depending on whether the substring from index i to j is palindromic or not.

Algorithm:

1. Base case is that each single character is a palindrome itself.

2. For length of two, if the two characters are equal then dp[i][i+1]=3 and p[i][i+1]=true, else if characters are different then dp[i][i+1]=2, p[i][i+1]=false.

3. Now we compute for the higher length substrings. If the start and end is matching and rest of the substring is already palindrome then we return 1 + the count from remaining part and store this result in dp[start][end] and also make p[start][end] true.
   If the start and end is not matching or the rest of the substring is not palindromethen we return the count from remaining part and store this result in dp[start][end] and also make p[start][end] false.

4. Finally return the value stored in dp[0][n-1] to get the count of the number of palindromic substrings;

Implementation:

#include <bits/stdc++.h>
using namespace std;

int countPalindromicSubstrings(string str)
{

    int n = str.length();

    if (n == 0 || n == 1)
        return n;

    vector<vector<int> > dp(n);
    vector<vector<bool> > p(n);

    for (int i = 0; i < n; i++) {
        dp[i] = vector<int>(n);
        p[i] = vector<bool>(n);
    }
   

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
        p[i][i] = true;
        if (i == n - 1)
            break;
        if (str[i] == str[i + 1]) {
            dp[i][i + 1] = 3;
            p[i][i + 1] = true;
        }
        else {
            dp[i][i + 1] = 2;
            p[i][i + 1] = false;
        }
    }
    for (int l = 3; l <= n; l++) {
        for (int start = 0; start <= n - l; start++) {
            int end = start + l - 1;
            if (str[start] == str[end] && p[start + 1][end - 1]) {
                dp[start][end] = dp[start + 1][end] + dp[start][end - 1] - dp[start + 1][end - 1] + 1;
                p[start][end] = true;
            }
            else {
                dp[start][end] = dp[start + 1][end] + dp[start][end - 1] - dp[start + 1][end - 1];
                p[start][end] = false;
            }
        }
    }
    return dp[0][n - 1];
}

int main()
{
    
    string str;

    cin >> str;

    cout << countPalindromicSubstrings(str) ;
    

    return 0;
}

Time complexity: O(n^2)

Here as we use two 2-D array for dynamic programming, therefore the auxillary space required is O(n^2) and thus,

Space complexity: O(n^2)

We can also have a top down dynamic programming approach as discussed below.

Top-Down Approach DP:

Top Down DP is a memoized version of the recursive approach.

To implement the top-down approach we intialize two 2-D arrays:dp[n][n] and p[n][n] where n is the length of the string.

dp[i][j] stores the the count of palindromic substrings from i to j and p[i][j] stores 1 if the substring from i to j is palindromic and 0 if not.

Algorithm:

1. If i>j then no such substring is possible therefore we return 0;
2. If i==j then there is only a single character in the substring and as we know every character is a palindromic substring therefore we return 1;
3. else we have a higher length substring from i to j. We check if we have already done the computations for these value of i and j and if yes then return the value dp[i][j].
4. else if not now we check if the substring is palindrome or not.
5. If the substring from i to j is a palindrome then we increment the number of palindromic substrings by 1 and check for the substrings (i, j-1) and (i+1, j) and remove the common palindrome substring (i+1,j-1) and store the result in dp[i][j].
6. If the substring from i to j is not a palindrome then we check for rest palindromic substrings (i, j-1) and (i+1, j) and remove common palindrome substring (i+1 , j-1) and store the result in dp[i][j].

In addition to this, while finding if the substring from i to j is palindromic or not, we have a 2-D array p, where p[i][j] stores the result if the substring from i to j is palindromic or not if we have already done the computions because of overlapping subproblems.

Implementation:

#include <iostream>
#include<string>
using namespace std;

int p[100][100];
int dp[100][100];

bool isPalindrome(string str,int i,int j)
{  
    if (i > j)
        return 1;
    
    if (p[i][j] != -1)
        return p[i][j];
   
    if (str[i] != str[j])
        return p[i][j] = 0;
 
    return p[i][j] = isPalindrome(str, i + 1, j - 1);
}

int PalindromicSubstrings(int i, int j,string str){
   if(i>j) return 0;

   if(i==j) return 1;
   
   if(dp[i][j]!=-1) return dp[i][j];
  
   if(isPalindrome(str,i,j)) return dp[i][j]=PalindromicSubstrings(i+1,j,str)+ PalindromicSubstrings(i,j-1,str)+1-PalindromicSubstrings(i+1, j-1,str);

   else return dp[i][j]= PalindromicSubstrings(i+1,j,str)+ PalindromicSubstrings(i,j-1,str)-PalindromicSubstrings(i+1, j-1,str);
}   
int main() {

    string str;
    cin>>str;
    memset(p,-1,sizeof(p));
    memset(dp,-1,sizeof(dp));

    cout<<PalindromicSubstrings(0,str.length()-1,str);

}

As we have seen that using dynamic programming approach we get a space complexity of O(n^2).so let us now see if it is possible to get the same time complexity but a better space complexity using some other algorithm.

Using modified Manacher’s algorithm

Manacher's algorithm:
Manacher's algorithm is used to find the longest palindromic substring in a given string.

To find a palindrome we start from the center of the string and compare characters in both directions one by one. If corresponding characters on both sides (left and right of the center) match, then they will make a palindrome. To find Longest Palindromic Substring of a string of length n, we take each possible 2n + 1 centers, do the character match in both left and right directions at each centers and keep track of LPS. If we need to calculate Longest Palindromic Substring at each pivot positions from left to right, then palindrome’s symmetric property could help to avoid some of the unnecessary computations. If there is a palindrome of some length L centered at any position P, then we may not need to compare all characters in left and right side at position P+1 as we have already calculated LPS at positions before P and they can help to avoid some of the comparisons after position P. This algorithm is known as manacher's algorithm.

Modified manacher's algorithm:

The idea here is that we modify manacher's algorithm in such a way that we consider each character of input string as pivot which act as midpoint of a palindrome and expand it in both directions to find the count all palindromes of even and odd lengths rather than just finding the longest one.

Algorithm

1. We consider every character in the substring (str[i]) as the pivot point.
2. For odd lengths substring we consider str[i] to be the midpoint and for even length substrings, we consider str[i] and str[i+1] to be the midpoints.
3. We check if this substring is a palindrome, if yes increment the count and keep on expanding them in both the directions untill the substrings are palindromic.

Implementation:

Implementation of our algorithm using modified Manacher’s algorithm in C++:

#include <iostream>
#include <string>
#include <set>
using namespace std;

set<string> s;
int count=0;

void func(string str, int start, int end)
{
    
    while (start >= 0 && end < str.length() && str[start] == str[end])
    {
        
        count++;
 
        // Expand in both directions
        start--, end++;
    }
}
 

int countPalindromicSubstrings(string str)
{
 
    for (int i = 0; i < str.length(); i++)
    {
        // find all odd length palindrome with `str[i]` as a midpoint
        func(str, i, i);
 
        // find all even length palindrome with `str[i]` and `str[i+1]` as
        // its midpoints
        func(str, i, i + 1);
    }
 
    return count;
}
 
int main()
{
    string str ;
    cin>>str;
 
    cout<<countPalindromicSubstrings(str);
 
    return 0;
}

Time and Space complexity analysis

In this algorithm, we have 2n – 1 pivots (n pivots for odd-length substrings and n-1 pivots for even-length substrings) that act as mid-points for possible palindromic substrings. For each midpoint, we expand towards left and right one character at a time and expand the substring till the latest substring is not a palindrome. Therefore, for each pivot point, we look at a maximum of n characters. Thus, our algorithm takes O(n) time for each pivot, and there are O(n) pivots in the input string. Therefore the time complexity of our solution is O(n^2).

Since we’re not using any auxiliary space therefore the space complexity is O(1).

Time complexity: O(n^2)

Space complexity: O(1)

With this article at OpenGenus, you must have the complete idea of how to find the number of palindromic substrings in an efficient way.