Longest Palindromic Substring

[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]

I’ve started out with an attempt to solve this problem in O(n), turns out, that would be way too complicated to handle special cases…

Here is what I’ve tried: initialize a vector of int which stores the longest palindrome found ending at index i. That is, “abacaba” would give me [1,1,3,1,3,5,7], and I just need to scan through the whole array and get the max of the whole array. This seems to be a viable solution, because a sequence of char [start, end] is a palindrome, if and only if [start+1, end-1] is also one. However, considering the case where we have consecutive duplicated characters like “cccccc”, this can become much more complicated to handle.

A straightforward solution is to scan through the whole string, and try to develop a longest palindrome on its left side and right side. The key though, is to recognize that there are only two cases for each character, namely left and right side both starting from index i, or left = i-1 and right = i+1. The time complexity is O(n^{2}), acceptable in our case given the assumption that the maximum length of S is 1000.

class Solution {
    string developFromCenter(const string &s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--; right++;
        }

        return s.substr(left+1, right-left-1);
    }

public:
    string longestPalindrome(string s) {
        string res;
        if (s.empty())
            return res;

        for (int i=0; i<s.length(); ++i) {
            string s1 = developFromCenter(s, i, i);
            if (s1.length() > res.length())
                res = s1;

            string s2 = developFromCenter(s, i, i+1);
            if (s2.length() > res.length())
                res = s2;
        }

        return res;
    }
};
Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s