Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
1.1.
Example
2.
Naive Approach
2.1.
Implementation
2.2.
Time Complexity
2.3.
Space Complexity
3.
Efficient Approach
3.1.
Implementation
3.2.
Time Complexity
3.3.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Longest Palindromic Substring For Every Center

Author Jaglike Makkar
2 upvotes

Problem

You are given a string S of length N. There are (2 * N - 1) positions where a substring of S can be centered. Find the length of the longest palindromic substring centered at each of these centers. 

Note: For odd length strings, the center is the middle character and for even length strings, the center lies between two middle characters.

Example

Input: S = “abaa”

Output: 1 0 3 0 1 2 1

Explanation:

The above figure shows the positions of (2 * N - 1) = 7 centers for the given string. Now we have to find the length of the longest palindromic substring centered at each of these 7 centers.

  1. For the first center, the longest palindromic substring is “a”. Thus, the answer is 1.
  2. The only substring centered at the second center is “ab”, not a palindrome. So, the answer is 0.
  3. The longest palindromic substring centered here at the third center is “aba”, so the answer is 3.
  4. For the fourth center, there are no palindromic substrings centered, so the answer is 0.
  5. The substrings centered here are “a”, “baa” for the fifth center. Since “baa” is not a palindrome, the answer is 1.
  6. For the sixth center, the longest palindromic substring is “aa”. 
  7. For the seventh center, the longest palindromic substring is “a”.

Naive Approach

First, let us find the length of the longest palindromic substring for a fixed center. The first observation is that, for a fixed center, if a substring of length K is not a palindrome, then the substrings of length greater than K will also not be a palindrome. 

Thus, to find the longest palindromic substring, we can iterate over the length K and check if the substring of length K is a palindrome or not. If it is not a palindrome, we will break the loop, else we will increment the answer. 

How can we efficiently check if a substring of length K is a palindrome or not? Since we are checking for length K, all the substrings centered at this center having lengths less than K are palindromes. Thus, we only have to check if the left end and the right end of this substring are the same or not. By this, we can find the longest palindromic substring for one center in O(N).

We can now use the above approach for all (2 * N - 1) centers and find the length of the longest palindromic substring centered there.

Implementation

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

// Function to find length of longest palindromic substring
vector<int> solve(string s){
   int n=s.size();

   // Vector to store answer for every center
   vector<int> res(n*2-1);

   // Checking for odd length palindromes.
   for(int i=0;i<n;i++){
      int k=0;

      // If s[i-k] = s[i+k], increment k, else break
      while(i-k>=0 && i+k<n && s[i-k]==s[i+k])k++;
      res[i*2]=k*2-1;
   }

   // Checking for even length palindromes
   for(int i=0;i<n-1;i++){
      int k=0;
     
      // If s[i-k] = s[i+k], increment k, else break
      while(i-k>=0 && i+k+1<n && s[i-k]==s[i+k+1])k++;
      res[i*2+1]=k*2;
   }
   return res;
}

// Driver Code
int main(){
   string s = "abaa";
   auto res = solve(s);

   // Printing the length of the longest palindromic substring
   for(int i=0;i<res.size();i++){
      cout<<res[i]<<' ';
   }
   cout<<endl;
   return 0;
}

Output

1 0 3 0 1 2 1

Time Complexity

For every center, we are iterating over the length of the palindromic substring. A palindromic substring can have at most O(N) length and there are 2*N - 1 centers. Therefore, the time complexity of the above approach is O(N^2).

Space Complexity

We are declaring the res vector for storing the answer for each center, therefore, the space complexity is O(N).

Also check out - Substr C++

Efficient Approach

Prerequisite: Manacher’s Algorithm

We can use Manacher’s algorithm to efficiently find the length of the longest palindromic substring for each center. It can be used to find the longest palindromic substring for each center in O(N). 

Implementation

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
// Function to implement mancachers algorithm
vector<int> manacher(string s) {
    int n = s.size();
    s = "$" + s + "^";
 
    // d[i] = length of the longest palindromic substring centered at i
    vector<int> d(n + 2);
    int l = 0, r = -1;
    for(int i = 1; i <= n; i++) {
        d[i] = max(0, min(r - i, d[l + (r - i)]));
        while(s[i - d[i]] == s[i + d[i]]) {
            d[i]++;
        }
        if(i + d[i] > r) {
            l = i - d[i], r = i + d[i];
        }
    }
    return vector<int>(begin(d) + 1, end(d) - 1);
}
 
// Function to return maximum
void solve(string s){
    string t;
 
    // Appending # before and after each character
    for(auto c: s) {
        t += string("#") + c;
    }
 
    // Calling manacher on the modified string
    auto res = manacher(t + "#");
 
    /*
    l[i] will store the length of the longest palindromic substring
    centered at ith center
    */
    vector<int> l = vector<int>(begin(res) + 1, end(res) - 1);
 
    // Counting the number of strings
    for (auto i: l){
        cout<<i-1<<' ';
    }
    cout<<endl;
}
 
// Driver Code
int main(){
    string s = "abaa";
    solve(s);
    return 0;
}

Output

1 0 3 0 1 2 1

Time Complexity

The time complexity of Manacher’s algorithm is O(N). To find the length of the longest palindromic substring for each center, we have used Manacher’s algorithm once. Therefore, the time complexity of the above approach is O(N).

Space Complexity

For a string of size N, the number of centers is 2*N - 1. We have used a vector to store the answer for each of these centers. The space complexity of Manacher’s algorithm is also O(N). Therefore, the total space complexity of the above approach is O(N).

You can also read about Palindrome Number in Python here.

Refer to know about :  Longest common subsequence

FAQs

  1.  What is a palindromic string?
    A palindromic string is a string that reads the same forwards and backward. For eg. “abba”, “hannah”, “bob” are palindromes, while “home”, “face” are not palindromes.
  2.  What is Manacher’s Algorithm?
    Manacher’s algorithm is a string algorithm that is used to find the length of the longest palindromic substring for every ‘center’. The center is the middle element for odd length strings, and for even length strings, the center lies between the two central characters. 

Key Takeaways

In this article, we have extensively discussed how to find the length of the longest palindromic substring for every center. We first saw the naive approach that works in O(N^2) and then we optimized our solution using Manacher’s algorithm that reduced the time complexity to O(N). 

We also saw the implementations of both approaches in C++. If you would like to learn more, try the Longest Palindromic Subsequence problem & also check out our articles on Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass