#5 Longest Palindromic Substring

Description

tags: String, Dynamic Programming

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"

My solution

(Expand Around Center)

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int maxLen = 0;
        string ret;
        for (int i=0; i<n; i++) {
            int l = i, r = i;
            while (l > 0 && s[l-1] == s[i]) l--;
            while (r < n-1 && s[r+1] == s[i]) r++;
            while (l > 0 && r < n-1 && s[l-1] == s[r+1]) {
                l--;
                r++;
            }
            if ((r - l + 1) > maxLen) {
                maxLen = (r - l + 1);
                ret = s.substr(l, maxLen);
            }
        }
        return ret;
    }
};

Solution

Approach 1: Longest Common Substring

Approach 2: Brute Force

Time:
Space:

Approach 3: Dynamic Programming

Time:
Space:

Approach 4: Expand Around Center

Time:
Space:

Approach 5: Manacher's Algorithm

Time:
Space: