Tag Palindrome

Longest Palindromic Substring

Arunima Mandal Leave a comment

Note: The problem title is pretty self-explaining. Now as for the solution, it can be solved in the usual brute force method (for each starting and ending position) in O(N^3) time. Another way would be Dynamic Programming which results in O(N^2) for both time complexity and space complexity.

The following approach is also an intuitive one (though hard to come to mind at first) with better time and space complexities. It is called Expand Around Centre.

Since expanding a palindrome around its center could take O(n) time, and as we are expanding for every index of the string, the overall complexity is O(n^2). And the space complexity is O(1).

Code:

#include <bits/stdc++.h>

using namespace std;

int expandAroundCentre(string &s, int left, int right)
{
    while(left>=0 && right<s.size() && s[left]==s[right])
    {
        left--;
        right++;
    }
    return right-left-1;
}

string longestPalindrome(string s)
{
    if(s.size()==0) return "";
    int start=0, ans=0;
    for(int i=0; i<s.size(); i++)
    {
        int len1=expandAroundCentre(s,i,i); //for odd length
        int len2=expandAroundCentre(s,i,i+1); //for even length
        int len=max(len1,len2);
        if(len>ans) //if len is greater than previous palindromic length
        {
            start=i-(len-1)/2; //for left side of i
            ans=len;
        }
    }
    return s.substr(start,ans);
}

int main()
{
    string s;
    cin>>s;
    cout<<"The longest palndromic substring is "<<longestPalindrome(s)<<endl;
    return 0;
}