5. 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.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

把input string裡每個char位置都當作一個palindrome中心點往左右擴張看是否能形成palindrome，要考慮形成的palindrome長度為奇數和偶數的情形。

// Expand from the center
string longestPalindrome(string s) { // time: O(n^2); space: O(1)
    int n = s.size(), start = 0, max_len = 0;
    if (n < 2) return s;
    for (int i = 0; i < n; ++i) {
        helper(s, i, i, start, max_len); // odd length
        helper(s, i, i + 1, start, max_len); // even length
    }
    return s.substr(start, max_len);
}
void helper(string& s, int l, int r, int& start, int& max_len) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) {
        --l, ++r;
    }
    if (max_len < r - l - 1) {
        max_len = r - l - 1;
        start = l + 1;
    }
    return;
}

利用Dynamic programming的概念搭配一個2D vector掃描所有可能的palindrome組合，dp[i][j]代表string[i...j]是否為palindrome。 (i) dp[i][j] = true if i == j (ii) dp[i][j] = s[i] == s[j] if j = i + 1 (iii) dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1] if j > i + 1

// Dynamic programming
string longestPalindrome(string s) { // time: O(n^2); space: O(n^2)
    int n = s.size(), start = 0, max_len = 0;
    vector<vector<bool> > dp(n, vector<bool>(n, false)); // dp[i][j] means s[i...j] is palindrome
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            dp[i][j] = (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1]));
            if (dp[i][j] && j - i + 1 > max_len) {
                start = i;
                max_len = j - i + 1;
            }
        }
    }
    return s.substr(start, max_len);
}

// Dynamic programming
string longestPalindrome(string s) { // time: O(n^2); space: O(n^2)
    int n = s.size(), start = 0, max_len = 1;
    vector<vector<bool> > dp(n, vector<bool>(n, false)); // dp[i][j] meas s[i...j] is palindrome
    for (int j = 0; j < n; ++j) {
        dp[j][j] = true;
        for (int i = j - 1; i >= 0; --i) {
            dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
            if (dp[i][j] && j - i + 1 > max_len) {
                start = i;
                max_len = j - i + 1;
            }
        }
    }
    return s.substr(start, max_len);
}

Manacher演算法能達到O(n) time complexity。

// Manacher
string longestPalindrome(string s) { // time: O(n); space: O(n)
    // insert $#
    string t = "$#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    // process palindromic radius array
    vector<int> p(t.size(), 0);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    for (int i = 1; i < t.size(); ++i) {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
        while (t[i + p[i]] == t[i - p[i]]) ++p[i];
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }
    }
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

// Manacher Algorithm
string longestPalindrome(string s) { // time: O(n); space: O(n)
    string t = "$#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    vector<int> P(t.size(), 0);
    int C = 0, R = 0, resC = 0, resLen = 0;
    for (int i = 1; i < t.size(); ++i) {
        int mirr = 2 * C - i;
        if (i < R) P[i] = min(R - i, P[mirr]);
        while(t[i + (P[i] + 1)] == t[i - (P[i] + 1)]) ++P[i];
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
        if (resLen < P[i]) {
            resLen = P[i];
            resC = i;
        }
    }
    // cout << resLen << " " << resC;
    return s.substr((resC - resLen) / 2, resLen);
}