Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
2.1.
Example
3.
Solution Approach
3.1.
Approach 1: Using Manacher’s Algorithm
3.1.1.
C++ Implementation
3.1.2.
Complexities
3.2.
Approach 2: Using Suffix Tree
3.2.1.
C++ implementation
3.2.2.
Complexities
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Count Palindromes

Author Teesha Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A palindrome is a word, number, verse or sentence that reads the same whether we read it backwards or forwards. Two examples of palindrome are Malayalam and 1234321. It is a fundamental and valuable concept in programming.

Problem statement

A palindrome word can also be written as the concatenation of many small palindrome words. A single letter is also a palindrome. You are given string str, and you need to find the number of different possible palindromes that can be created using the string str. If the same palindrome appears multiple times, each one should be counted separately.

Example

Input

Malayalam

Output

15

Explanation

Here, some of the ways in which malayalam can be written as are: 

malayalam : m + a + l + aya + l + a + m

malayalam : m + ala + y + ala + m

If we count all the different palindromes for the word malayalam, we will get the result 15.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

Approach 1: Using Manacher’s Algorithm

Manacher’s algorithm is a string matching algorithm that works in linear time and is used to find the longest palindromic substring. The idea is that you take each point in the string as a midpoint and expand the string in both directions to find the longest palindromic substring. We can modify the manacher’s algorithm to count the number of different palindromes created from the string S by considering all the palindromes and not just the longest one. Let’s discuss the steps to implement modified Manacher’s algorithm to solve this problem.

The steps of implementation are:

  • Take the input string str
     
  • Declare a character array s and int array p. Set s[0] to ‘$’ and s[1] to ‘#’. Run a loop for i from 0 to length of string and store str[i] to s[i*2 +2] and ‘#’ to s[i*2+3]. Set the last index of s as ‘\0’. Use the memset function to initialise p array with 0. Initialise id and MaxL with 0.
     
  • Implement a for loop from i equal to 0 to the length of s. If p[id] + id is greater than i then update p[i] with the minimum value of p[2*id-i] and p[id] + id - i. Otherwise update p[i] by 1. While s[i + p[i]] is equal to s[i-p[i]] increment p[i]. Now if p[i] +1 > p[id] + id, update id with i. Add half of p[i] to MaxL.
     
  • Print the answer which is the value stored in MaxL.

C++ Implementation

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;  
//defining important data structures
const int maxn = 1005;
char str[maxn];
char s[maxn*2];
int p[maxn*2];
int len;
 
//modified manacher’s algorithm
void Manacher(){
    int i;
    s[0] = '$';
    s[1] = '#';
    len = strlen(str);
    //define s from str
    for(i=0; i<len; i++) {
        s[i*2 +2] = str[i];
        s[i*2 +3] = '#';
    }
    len = i*2+2;
    s[len] = '\0'; //To denote the end of string
    int MaxL, id = 0;
    MaxL =0;
    //memset initialises p with 0 for all indices
    memset(p,0,sizeof(p));
    //i is the position of center element for current palindrome
    for(int i=0; i<len; i++) {
        if(p[id] + id > i)
            p[i] = min(p[2*id-i], p[id] + id -i);
        else
            p[i] = 1;
        while(s[i+p[i]] == s[i-p[i]])
            p[i]++;
        if(p[i] + i > p[id]+id) {
            id = i;
        }
        MaxL += p[i]/2;
    }
    //print answer
    cout<<MaxL<<endl;
}
int main(){
    //Taking input
    scanf("%s", str);
    Manacher();
}


Input

malayalam


Output 

15

Complexities

Time Complexity

O(n), where n denotes the length of the input string

Reason: The total middle positions to check for palindromes are linear; hence the complexity of the algorithm is linear. 

Space Complexity 

O(n), where n denotes the length of the input string.

Reason: To store the input string and define s and p, we require linear space; therefore, the complexity is O(n).

Also check out - Substr C++ and Rabin Karp Algorithm

Approach 2: Using Suffix Tree

Another approach to solving this problem is using a suffix tree. A suffix tree is a data structure that is similar to trie, but it has all the suffixes of a text as its key. With the help of Ukkonen's Algorithm, we can construct the suffix tree in the worst-case time complexity of O(N).

The steps of implementation are:

  • Take the input string in s and store the length of s in variable len.
     
  • Initialise the suffix tree that we will use in solving this problem with the initTree function and set ans to 0.
     
  • Run a for loop over the input string and call the addLetter function for each letter of the input string. addLetter function takes the position of the current letter and modifies our suffix tree accordingly.
     
  • For each letter in the input string, increment the value of ans by the value of num of the tree[suff].
     
  • Print the answer that is stored in ans variable.

C++ implementation

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
 
using namespace std;
#define MAX 1005
//node structure used to buildup the tree
struct Node
{
    int next[26];
    int len;
    int sufflink;
    int num;
}tree[MAX];
char s[MAX];
 
int num;
int suff;
//Function that adds the letter at the ,pos position by modifying the suffix tree
bool addLetter(int pos)
{
    int cur=suff,curlen=0;
    int let=s[pos]-'a';
 
    while(1)
    {
        curlen=tree[cur].len;
        if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
            break;
        cur=tree[cur].sufflink;
    }
    if(tree[cur].next[let])
    {
        suff=tree[cur].next[let];
        return false;
    }
    num++;
    suff=num;
    tree[num].len=tree[cur].len+2;
    tree[cur].next[let]=num;
    if(tree[num].len==1)
    {
        tree[num].sufflink=2;
        tree[num].num=1;
        return true;
    }
    while(1)
    {
        cur=tree[cur].sufflink;
        curlen=tree[cur].len;
        if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
        {
            tree[num].sufflink=tree[cur].next[let];
            break;
        }
    }
    tree[num].num=1+tree[tree[num].sufflink].num;
    return true;
 
}
//A function to initialize the suffix tree
void initTree()
{
    num=2;suff=2;
    tree[1].len=-1;tree[1].sufflink=1;
    tree[2].len=0;tree[2].sufflink=1;
}
int main()
{
    //Taking input
    scanf("%s",s);
    int len=strlen(s);

    //Initializing the suffix tree
    initTree();
    long long int ans=0;

    //Loop over the input string
    for(int i=0;i<len;i++)
    {
         addLetter(i);
         ans+=tree[suff].num;
    }

    //printing the output
    printf("%d\n",ans);
    return 0;
}


Input

malayalam


Output 

15

Complexities

Time Complexity

O(N logN), where N denotes the length of the input string

Reason: For running a for loop over the input string, e get the time complexity of O(N), then for searching in suffix tree we have the complexity of O(logN); Therefore the overall time complexity of this program is O(NlogN).

Space Complexity 

O(n), where n denotes the length of the input string.

Reason: To store the input string we require linear space; therefore, the complexity is O(n).

 

Also see, Morris Traversal for Inorder.

You can also read about Palindrome Number in Python here.

FAQs

  1. What is a palindromic string?
    A string that is a palindrome is called a palindromic string. A palindrome is a word, number, verse or sentence that reads the same backward and forwards.
     
  2. What is the use of the manacher’s algorithm?
    Manacher’s algorithm is used to find the longest palindromic substring of a string in linear time. It can be modified to find solutions to the problems of counting palindromes.
     
  3. What are the time and space complexity of the manacher’s algorithm?
    The time complexity of the manacher’s algorithm is O(n) because the total middle points to check for palindromes is 2n+1. The space complexity is O(n).
     
  4. What does the memset function in c++ do?
    The memset function in c++ takes an object, a character, and a positive integer num in three arguments. It copies the character in the object num times. It is defined in <cstring> header file.
     
  5. How many centre points are there in the manacher’s algorithm?
    In the manacher’s algorithm, there are 2n+1 centres and not n centres. The reason is that for palindromes with the odd number of letters, there are n centres, and for an even number of letters, centres are between two characters.
     
  6. Can a single character be a palindrome?
    Yes, a single character is considered a palindrome because it reads the same forward and backwards.

Key Takeaways

This article discusses the most optimised solution of the problem Count Palindromes using Manacher’s Algorithm. We took advantage of mirror indexing and reused precomputed data when a palindrome exists inside another palindrome. 

Check out this problem - Check If A String Is Palindrome

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Car Fleet
Next article
Count of Longest Palindromic Substrings
Live masterclass