# 5 - Longest Palindromic Substring

解法一 - 暴力法

這一題跟 516 不一樣的地方在於，這提要求的是 substring，所以必須是連續的字母。所以可以分成兩種 case：

1. 頭跟尾的字母相同：分別把頭跟尾都往內移，然後繼續確認目前這個是不是 palindromic substring

2. 頭跟尾的字母不同：那就把頭往後移 & 尾往前移，然後分別確認兩個新產生的字串是不是 palindromic substring

實作如下：

class Solution {
public:
    string longestPalindrome(string s) {
        return findLPSLength(s, 0, s.length()-1);
    }

private:
    string findLPSLength(string& s, int start, int end) {
        string res = "";
        if(start > end)
            return res;

        if(start == end) {
            res = "";
            res += s[start]; 
            return res;
        }

        int c1 = 0;
        if(s[start] == s[end]) {
            int remainLength = (end-start+1) - 2;
            if(remainLength == findLPSLength(s, start+1, end-1).length())
                c1 = remainLength+2;
        }

        string s2 = findLPSLength(s, start+1, end);
        string s3 = findLPSLength(s, start, end-1);
        int c2 = s2.length();
        int c3 = s3.length();

        int maxVal = max(c1, max(c2, c3)); 
        if(maxVal == c1 && maxVal > 0) res = s.substr(start, end-start+1);
        else if(maxVal == c2  && maxVal > 0) res = s2;
        else if(maxVal == c3  && maxVal > 0) res = s3;

        return res;
    }
};

不意外地，這個做法會 TLE。

解法二 - DP

class Solution {
public:
    string longestPalindrome(string s) {
        string res = "";
        if(s.empty()) return res;
        res += s[0];
        int maxLen = 1;

        // Init
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i=0; i<n; i++) {
            dp[i][i] = true;
        }

        // Build dp table
        for(int start = n-1; start>=0; start--) {
            for(int end=start+1; end<n; end++) {
                if(s[start] == s[end]) {
                    // If the length of current string == 2
                    // Or the remaining string is also palindrome
                    if(end-start == 1 || dp[start+1][end-1] == true) {
                        dp[start][end] = true;
                        if(end-start+1 > maxLen) {
                            maxLen = end-start+1;
                            res = s.substr(start, end-start+1);
                        }
                    }
                }
            }
        }

        return res;
    }
};

解法三 - Manacher's algorithm

可以見 [Wikipedia](https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm)，但這解法有點小複雜。