[LeetCode] Longest Palindromic Substring

Link : Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Analysis:

First thought is brute force. For every kind selection of start point and end point, there are totally O(N*N) and each palindrome recognition is O(N). And total time complexity is O(N^3). Test proved it's too slow.

Second try. Because Palindrome has special property, symmetric. If a long string is a Palindrome, the sub-string in its center has to be a sub-string. Or in another way, if its sub-string in the middle is not a palindrome, the large one cannot be, thus avoiding a lot of unnecessary comparison.



Code right on the way. Code1

This is not dynamic programming, but its idea is quite similar to check the result we have already got. The only difference is dynamic programming has a data structure to store these result, while in this example, the result(whether the sub-string in the center is a palindrome or not) is reused in the next comparison. Actually, we simplify it by putting all of them in the while loop.

P.S.
Manacher algorithm is available to solve this problem in linear time. It solves this problem by making use of the symmetric property but in much deeper degree. I looked at several articles, they explain it but I don't think they get the learner to the point.
http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

The best way to learn it is by doing the algorithm by hand by yourself.
When going through left to right. Every time we get a new center i to expand, if it is not covered by previous expansion E(with a center C, a right most covered position R), no workload is reduced.. 
1)work is not even reduced if i is not covered by expansion E

If it is covered by expansion E, it has a symmetric position 2C-i. They have similar(but possibly not identical) expansion, and work is done there(partially). 
1) we are done if the expansion of 2C-i is fully covered by expansion E
2) work is reduced but there still some more if expansion E cannot cover all of expansion of 2C-i

Code1

 
class Solution {
    public:
    std::string longestPalindrome(std::string s) {
        if(s.size()==0)
        return "";
        int n = s.size();
        int max = 0, left = 0, right = 0;
        std::string maxstr="";
        for(int i=0; i<n; i++)
        {
            int l = i, r = i;
            if(center(s,l,r)&&r-l+1>max)
            {
                max = r-l+1;
                left = l;
                right = r;
            }
            l = i+1, r = i;
            if(center(s,l,r)&&r-l+1>max)
            {
                max = r-l+1;
                left = l;
                right = r;
            }
        }
        maxstr = s.substr(left, max);
        return maxstr;
    }
    
    bool center(std::string s, int& l, int& r) {
        if(s.size()==0)
        return true;
        int n = s.size();
        while(l-1>=0&&r+1<n&&s[l-1]==s[r+1])
        {
            l--;
            r++;
        }
        return r>=l;
    }
};

I still find it time consuming if need to look at all of the possible sub-string up to now. For example, 8234329. If we find a sub-string 23432, and expand it cannot get a longer palindrome, no need to go further searching because no other one will be longer than it. The reason is that for another possible palindrome, we either move its center backward or forward. But due to boundary constraint, other palindrome sub-string cannot be longer than 5. The max one-half length on one side is min(i-0+1, n-1-i).
8234329 8234329
00↑0000 0000↑00
I test it and running time is reduced.

Another idea would be, why do we start from one side, why not start from the center!? Because if we have found one long enough, no need to care about other shorter one on sides! And because we start from the center, it is more likely to get the longest and reduce later work.

 

#include <iostream>
#include <string>

class Solution {
    public:
    std::string longestPalindrome(std::string s) {
        if(s.size()==0)
            return "";
        int n = s.size();
        int max = 0, left = 0, right = 0;
        std::string maxstr="";
        for(int i=0; i<n; i++)
        {
            int len = (i-0+1)<(n-1-i)?(i-0+1):(n-1-i);   ////  here is the change
            if(len<max/2)                                ////  here is the change
                break;                                      ////  here is the change
            int l = i, r = i;
            if(center(s,l,r)&&r-l+1>max)
            {
                max = r-l+1;
                left = l;
                right = r;
            }
            l = i+1, r = i;
            if(center(s,l,r)&&r-l+1>max)
            {
                max = r-l+1;
                left = l;
                right = r;
            }
        }
        maxstr = s.substr(left, max);
        return maxstr;
    }
    
    bool center(std::string s, int& l, int& r) {
        if(s.size()==0)
        return true;
        int n = s.size();
        while(l-1>=0&&r+1<n&&s[l-1]==s[r+1])
        {
            l--;
            r++;
        }
        return r>=l;
    }
};