Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1: Brute force
3.1.
C++ implementation
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time complexity
3.2.2.
Space complexity
4.
Approach 2: Expand around the center method
4.1.
C++ implementation
4.1.1.
Input
4.1.2.
Output
4.2.
Complexities
4.2.1.
Time complexity
4.2.2.
Space complexity
5.
Approach 3: Using Dynamic Programming
5.1.
C++ implementation
5.1.1.
Input
5.1.2.
Output
5.2.
Complexities
5.2.1.
Time complexity
5.2.2.
Space complexity
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

Count of Longest Palindromic Substrings

Author Shreya Deep
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

A palindrome sequence of characters reads the same in both forward and reverse directions. For example, “anna.” On both backward and forward reading, it’s “anna.” A substring is a contiguous part of a string. Let’s discuss a problem based on these two terms.

Problem Statement

Given a string s, find the length of the longest palindromic substring of the string and also find the number of palindromic substrings of that length.

For example,

Input
s = “babad”

Output
3 1

Explanation: The given string is “babad”. The substring “bab” is a palindrome, and it’s also the only palindromic substring of this maximum length. So the answer is 3 (maximum length of palindromic substring) and 1 (the number of maximum length palindromic substrings).

Also see, C Programming

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

Approach 1: Brute force

The brute force approach to solve this problem is to find all the substrings and, for each substring, check if it’s a palindrome or not. If yes, then check if it’s by far the maximum length palindrome substring or not. Update the maximum length. Once we have found the maximum length, find all the palindromic substrings of this length and increase the count by 1 each time such string is found.

C++ implementation

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

bool isPalindrome(string temp){
    int n = temp.length();
    for (int i = 0; i < n/ 2; i++) {
        /* if the charcters at index i and n-i-1 are not equal, return false*/
        if (temp[i] != temp[n - i - 1]) {
            return false;
        }
    }
    
    /* Else return true*/
    return true;
}


int main()
{
    string s;
    cin>>s;
    int mxlength = 0; 
    
    /* Variable for storing the maximum length of palindromic substring */
    int n = s.length();
    
    /* Traverse all the substrings*/
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            string temp = s.substr(i,j-i+1);
            if(isPalindrome(temp)){ 
            /* if the current substring is a palindrome: update the value of maximum length */
                int len = j-i+1;
                mxlength = max(mxlength,len);
            }
        }
    }


    /* variable the stores the number of palindrome substrings of length mxlength*/
    int cnt=0;
    /* For all the substrings of length mxlength, check how many of them are palindromic. cnt is equal to that number only */
    for(int i=0;i<=n-mxlength;i++){
        string temp = s.substr(i,mxlength);
        if(isPalindrome(temp)){
            cnt++;
        }
    }
    cout<<mxlength<<" "<<cnt<<endl;
    return 0;
}

Input

cabaabad

Output

6 1

Complexities

Time complexity

O(n^3), where n is the length of the given string

Reason: To go through all the substrings one by one takes O(n^3) time. 

Space complexity

O(1)

Reason: No extra variable space is taken.

 

Also see, Morris Traversal for Inorder and Rabin Karp Algorithm.

Approach 2: Expand around the center method

In this approach, we try to move around an index on both left and right sides and check if the characters on the left and right sides are equal.

The point to take care of is that, here, we’re considering the current index element as the mid of the palindromic string. But, there can be even length palindromic substrings also. In that case, there is no mid character of the palindromic substring. So, in this case, we will assume a space as a mid-character and check if the characters on the left and right of that space are equal or not. 

Let’s understand with an example:

Suppose the string is: “cabaabad”.

Therefore, it is also important to check for even length strings.

Now, let’s discuss how exactly do we check?

  • For even length substrings: We keep a variable as len, which stores the length till which we can extend in both sides of the character we’re taking as the middle element. Every time we have the left and right character equal (s[i-len]==s[i+1+len]), the new length of the current palindromic substring will be 2*len+2, and we increase the value of len by 1. 
     
  • For odd length substrings: We keep a variable as len, which stores the length until which we can extend in both sides of the character we’re taking as the middle element. Every time we have the left and right character equal (s[i-len]==s[i+len]), the new length of the current palindromic substring will be 2*len+1, and we increase the value of len by 1. 
     

Once we’ve found the length of the longest palindromic substring, we can look up all the substrings of that length and see how many of them are palindromic. That count will be the second number in the output.

C++ implementation

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

bool isPalindrome(string temp){
    int n = temp.length();
    for (int i = 0; i < n/ 2; i++) {
        /* if the charcters at index i and n-i-1 are not equal, return false*/
        if (temp[i] != temp[n - i - 1]) {
            return false;
        }
    }
    
    /* Else return true*/
    return true;
}


/* This is the function that return the maximum length of the palindromic substring of this string */
int maxLengthOfPalindromicSubstring(string s) {
    int length = 0;
    int len = 0;
    /* if the size is two or less, check for the case where the size is two and its two characters are the same */
    if (s.size() == 2 and s[0] == s[1]) {
        return 2;
    }
    /* if not, only one element is in the longest palindromic substring, so return 1*/
    else if (s.size() < 3) {
        string c(1, s[0]);
        return 1;
    }
        
    string temp;
        
    /*The technique is that, we find a Palindrome string which has size of 2 or 3. If it's a palindrome string, we will try to check if we can extend its length to its both side to find if the extended string is also a palindrome */
    for (int i = 0; i < s.size() - 1; i++) {
        len = 0;
        /* This is for the case where the size of the longest string might be an even number. smallest size possible: 2*/
        while ((i-len) >= 0 and (i+1+len) < s.size() and s[i-len] == s[i+1+len]) {
            if (length < 2*len+2){
                length = 2*len+2;
                temp = s.substr(i-len, length);
            }
            len++;
        }
        len = 0;
        /* This is for the case where the size of the longest string might be an odd number. smallest size possible: 3 */
        while ((i-len >= 0) and (i+len < s.size()) and s[i-len] == s[i+len]) {
            if (length < 2*len+1) {
                length = 2*len+1;
                temp = s.substr(i-len, length);
            }
            len++;
        }
    }
    return temp.length();
}


int main()
{
    string s;
    cin>>s;
    int n = s.length();
    int mxlength = maxLengthOfPalindromicSubstring(s); 
    
    /* variable the stores the number of palindrome substrings of length mxlength*/
    int cnt=0;
    /* For all the substrings of length mxlength, check how many of them are palindromic. cnt is equal to that number only */
    for(int i=0;i<=n-mxlength;i++){
        string temp = s.substr(i,mxlength);
        if(isPalindrome(temp)){
            cnt++;
        }
    }
    cout<<mxlength<<" "<<cnt<<endl;
    return 0;
}

Input

cabaabad

Output

6 1

Complexities

Time complexity

O(n^2), where n is the length of the given string

Reason: For each index i, it takes O(n) time in the worst case to find the maximum length till which we can go on both sides. And there are a total of n indices. Therefore, the total time complexity will be O(n^2).

Space complexity

O(1)

Reason: No extra variable space is taken.

Also check out - Substr C++

Approach 3: Using Dynamic Programming

The idea is to store the information of a substring from index i to index j in a dp array. So basically, the value of dp[i][j] will be 1 if the substring from index i to j is a palindrome. Otherwise, it will be 0. 

  • The recurrence relation will be that, for dp[i][j], we will check if s[i]==s[j] and dp[i+1][j-1]==1. Because for the substring from index i to j to be a palindrome, the last two characters should be equal, and also, the substring from i+1 and j-1 should be a palindrome in itself. In this way, we can find the value of all dp[i][j] for all i from 0 to n and all j from 0 to n (where n is the length of the string). 
     
  • The base case is all dp[i][i] =1 because the substring from index i to i will be a one character substring, and it will be a palindrome for sure. Also, we will have to initially find the value of dp[i][i+1] as a base case since the recurrence relation is not applicable here. So, we will traverse the whole string once, and, for each index i, we will see if s[i]==s[i+1]. If yes, then, dp[i][i+1]=1, otherwise 0.


Using the above method, the maximum length of the palindromic substring is found. Now, let the length be l, then we can find the number of palindromic substring with this length by traversing all i and for each i, checking if dp[i][i+l-]==1. If yes, then increase the count by 1. 

C++ implementation

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

bool isPalindrome(string temp){
    int n = temp.length();
    for (int i = 0; i < n/ 2; i++) {
        /* if the charcters at index i and n-i-1 are not equal, return false*/
        if (temp[i] != temp[n - i - 1]) {
            return false;
        }
    }
    
    /* Else return true*/
    return true;
}


/* This is the function that return the maximum length of the palindromic substring of this string */
int maxLengthOfPalindromicSubstring(string s) {
    int sz = s.size();


    // Base Case Length 1
    if(sz == 1) return 1;
        
    // Base Case Length 2
    if(sz == 2 && s[0] == s[1]) return 2;
    if(sz == 2 && s[0] != s[1]){
        return 2;
    }
    int longest = 1;


    /* Dp array for storing if the substring from index i to j is a palindrome or not*/
    bool dp[1000][1000] = {0,};  
    
    /* For all length 2 substrings */
    for(int i = 1;i<sz;++i){
        if(s[i-1]==s[i]){
            dp[i-1][i] = 1;
            longest = 2;
        }
        else{
            dp[i-1][i] = 0;
        }
    }
    
    for(int i = sz-1;i>=0;i--){
        for(int j = i+1;j<sz;j++){        
            if(s[j] == s[i] && dp[i+1][j-1] == 1){
                dp[i][j] = 1;
                if(longest<(j-i+1)){
                    longest = j-i+1;
                }
            }
        }
    }
    return longest;
}


int main()
{
    string s;
    cin>>s;
    int n = s.length();
    int mxlength = maxLengthOfPalindromicSubstring(s); 
    
    /* variable the stores the number of palindrome substrings of length mxlength*/
    int cnt=0;
    /* For all the substrings of length mxlength, check how many of them are palindromic. cnt is equal to that number only */
    for(int i=0;i<=n-mxlength;i++){
        string temp = s.substr(i,mxlength);
        if(isPalindrome(temp)){
            cnt++;
        }
    }
    cout<<mxlength<<" "<<cnt<<endl;
    return 0;
}

Input

cabaabad

Output

6 1

Complexities

Time complexity

O(n^2), where n is the length of the given string

Reason: Calculating the value of all dp[i][j] takes O(n^2) time.

Space complexity

O(n^2), where n is the length of the given string

Reason: Only space taken is by the dp array, and it is O(n^2).

You can also read about Palindrome Number in Python here.

FAQs

  1. What is dynamic programming?
    Dynamic programming is a programming technique used to optimize the solution of problems by remembering the solutions to the subproblems that occur repeatedly and again, hence avoiding solving the same subproblem repeatedly. 
     
  2. What is a palindrome?
    A palindrome sequence of characters reads the same in both forward and reverse directions. For example, “anna.” On both backward and forward reading, it’s “anna.”
     
  3. Is a one-length string always a palindrome?
    Yes, a one-length string is always a palindrome because it reads the same in forwards and backward reading. For example, “a” reads “a” from both front and back both.
     
  4. What is a substring?
    A substring is a contiguous part of a string. For example, for string “abbbaba”, the strings “abba”, “baba”, and “bbb” are different substrings.
     
  5. What is a palindromic substring?
    A substring that reads the same in both forward and reverse directions, i.e., is a palindrome, is called a palindromic substring.

Key Takeaways

In this article, we have discussed the problem of finding all the longest palindromic substrings. Expanding around the center and Dynamic programming are the two methods discussed here. This problem can also be solved using Manacher’s algorithm. You can read about the algorithm here and try to write the code. 

Check out this problem - Check If A String Is Palindrome

Check out this problem - Frog Jump

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!

Live masterclass