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.
- For the first center, the longest palindromic substring is “a”. Thus, the answer is 1.
- The only substring centered at the second center is “ab”, not a palindrome. So, the answer is 0.
- The longest palindromic substring centered here at the third center is “aba”, so the answer is 3.
- For the fourth center, there are no palindromic substrings centered, so the answer is 0.
- The substrings centered here are “a”, “baa” for the fifth center. Since “baa” is not a palindrome, the answer is 1.
- For the sixth center, the longest palindromic substring is “aa”.
- 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++