005. Longest Palindromic Substring

Difficulty: Medium

Frequency: Medium

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.

Test cases:
1. a
2. aa
3. aaa
4. aba
5. abba

Solution 1:

Data structure:
string
Method:
Two pointers
Steps:
1. For each center, expand and test whether it is a palindrome and then record its length if it is the current max.
Complexity:
Runtime: O(n^2) 168 ms
Space: O(1)
Code:
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;
        string result;
        for (int i = 0; i < 2 * n - 1; i++) {
            int left = i / 2 - (i + 1) % 2, right = i / 2 + 1;
            while (left >= 0 && right < n) {
                if (s[left] != s[right]) break;
                else {
                    left--;
                    right++;
                    result = result.size() < right - left - 1 ? s.substr(left + 1, right - left - 1): result;
                }
            }
        }
        return result;
    }
};

Solution 2:
Data structure:
string
Method:
Manacher’s algorithm
steps:
see links.
Complexity:
Runtime: O(n) 16 ms
Space: O(n)
Code:
class Solution {
public:
    string longestPalindrome(string s) {
        string t;
        for (int i = 0; i < s.size(); i++) {
            t += "#" + s.substr(i, 1);
        }
        t.push_back('#');
        
        vector<int> p(t.size(), 0);
        int center = 0, boundry = 0, maxLen = 0, resCenter = 0;
        for (int i = 1; i < t.size() - 1; i++) {
            int iMirror = 2 * center - i;
            p[i] = boundry - i > 0 ? min(boundry - i, p[iMirror]) : 0;
            // expand p[i]
            while (i - 1 - p[i] >= 0 && i + 1 + p[i] <= t.size() - 1 && t[i - 1 - p[i]] == t[i + 1 + p[i]]) {
                p[i]++;
            }
            // update center and boundry
            if (p[i] + i > boundry) {
                boundry = p[i] + i;
                center = i;
            }
            if (p[i] > maxLen) {
                maxLen = p[i];
                resCenter = i;
            }
        }
        return s.substr((resCenter - maxLen) / 2, maxLen);
    }
};

Submission errors:
1. seg fault. Need to be careful with the range.
2. TLE. Solution is not good enough.

Things to learn:

1. When need to handle even and odd in string or array, examples will help.
2. Manacher’s algorithm is quite interesting, but don’t know whether it is useful for other problems.
Advertisements

2 thoughts on “005. Longest Palindromic Substring

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