# 5. Longest Palindromic Substring

Given a strings, find the longest palindromic substring ins. You may assume that the maximum length ofsis 1000.

Example:

``````Input:

Output:
"bab"

Note:
"aba" is also a valid answer.
``````

Example:

``````Input:
"cbbd"

Output:
"bb"
``````

Thoughs:

1. similar to 647. Number of palindromic substring
2. O(n^2) with DP or center expansion, O(n) with Manacher’s algorithm
3. the number between left and right (exclusive) is "right - left - 1" and number from left and right (inclusive) is "right - left + 1"

Code (O (n^2) DP)

``````class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
string ans = "";
bool d[n][n] = {{false}};
for(int i = n; i >= 0; i--){
for(int j = i; j < n; j++){
d[i][j] = (s[i] == s[j]) && (j - i < 3 || d[i+1][j-1]);
if(d[i][j] && j - i + 1 > ans.length())
ans = s.substr(i,j - i + 1); // +1 since end exlusive
}
}

return ans;
}
};
``````

Code (O (n^2) without extra space)

``````class Solution {
public:
string longestPalindrome(string s) {
string ans = "";
for(int i = 0; i < s.length() ; i ++){
string s1 = extend(s,i,i), s2 = extend(s, i, i+1);

if(s1.length() > ans.length()) ans = s1;
if(s2.length() > ans.length()) ans = s2;
}

return ans;
}

string extend(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);
}
};
``````

Code (O(n)) with Manacher's algorithm

``````class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# For example, s = "abba", A = "@#a#b#b#a#\$".
A = '#'.join('@{}\$'.format(s))
Z = [0] * len(A)
# print "%s\n%s"%(A,Z)
center = right = 0
for i in xrange(1, len(A) - 1):
# get the palindrome numbers based on right boundary
# and mirror palindrome
if i < right:
Z[i] = min(right - i, Z[2 * center - i])
#equivalent to: Z[i] = (right > i) and min(right - i, P[2*center - i])

# explore the palindrome at current pivot
while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
Z[i] += 1

# update right boundary
if i + Z[i] > right:
center, right = i, i + Z[i]

maxlen, center = max((n, i) for i , n in enumerate(Z))
return s[(center - maxlen)//2:(center + maxlen)//2 ]
``````