Longest Palindromic Substring

Problem

Write a function that, given an input string, locates and returns the longest sequence in the string that is a palindrome.

Solution

Every sub-string starting from the longest to the shortest needs to checked as shown below

bool is_palindrome(string const& str, size_t i,size_t n);
string max_sub_palindrome(string const& str)
   {
       size_t N = str.length();
       for(size_t n=N; n>0; --n)
       {
          for (size_t i=0; i+n <=N; ++i)
            if (is_palindrome(str,i,n))
              return str.substr(i,n);
       }
       return string();
   }

is_palindrome can be computed recursively as shown below

bool is_palindrome(string const& str, size_t i,size_t n)
   {
     if (n<=1)
       return true;
     else
       return str[i]==str[i+n-1] &&
              is_palindrome(str,i+1,n-2);
   }

The above implementation of is_palindrome has O(n) time complexity.
Thus max_sub_palindrome has O(N3) time complexity where N is the length of the string. Notice however that is_palindrome is can be memoised as follows:

class Search
{
    public:
        Search(size_t n):N(n),arr(n*n)
    { }
        bool operator() (string const& str, size_t i,size_t n)
        {
            if (n<=1)
                return true;
            else if (Get(i,n))
                return false;
            else if( str[i]==str[i+n-1])
            { 
                auto k =  operator()(str,i+1,n-2);
                if (k) 
                    return k;
                else
                {
                    Set(i,n);
                    return k;
                }
            }
            else
            {
                Set(i,n);
                return false;
            }
        }
    private:
        bool Get (size_t i, size_t j)
        {
            return arr[i*N+j-1];
        }
        void Set (size_t i, size_t j)
        {
            arr[i*N+j-1]=true;
            std::cout<<i<<","<<j<<std::endl;
        }
        std::vector<bool> arr;
        size_t N;

};

I would like to draw your attention to Line 19 and Line 25, where we flag that the sub-string commencing at i of length n is not a palindrome. We make use of that fact in Line 10 so as to avoid calling the operator() recursively if the specific problem has already been visited. We could have implemented the class as a closure in any language that supports it, which is almost all languages except C/C++.
The main function is same, save for the marked line as shown below:

string max_sub_palindrome(string const& str)
{
    size_t N = str.length();
    Search is_palindrome(N);  ///<---added     
    for(size_t n=N; n>0; --n)
    {
        for (size_t i=0; i+n <=N; ++i)
        { 
            if(is_palindrome(str,i,n))
                return str.substr(i,n);
        }
    }
    return std::string();
}

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Longest Palindromic Substring

  1. Roopak Selvanathan says:

    Can use Dynamic Programming. Very similar to matrix multiplication using DP algorithm.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s