# 5. Longest Palindromic Substring

## 題目敘述

Given a string `s`, return the longest palindromic substring in `s`.

Example 1:

``````Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
``````

Example 2:

``````Input: s = "cbbd"
Output: "bb"
``````

Constraints:

• `1 <= s.length <= 1000`
• `s` consist of only digits and English letters.

Hint 1:

How can we reuse a previously computed palindrome to compute a larger palindrome?

Hint 2:

If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

Hint 3:

Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation?

## 解法解析

### 解法範例

#### Go

##### Expand Around Center
``````func longestPalindrome(s string) string {
if len(s) < 2 {
return s
}
start, end := 0, 0
for i := 0; i < len(s); i++ {
len1 := expandAroundCounter(s, i, i)
len2 := expandAroundCounter(s, i, i+1)
var length int = len2
if len1 > len2 {
length = len1
}
if length > end-start {
start = i - (length-1)/2
end = i + length/2
}
}
return s[start : end+1]
}

func expandAroundCounter(s string, left int, right int) int {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
return right - left - 1
}
``````
##### Manacher's Algorithm
``````func longestPalindrome(s string) string {
var expandStr string = "#"
for _, c := range s {
expandStr += string(c) + "#"
}
var maxLen int = len(expandStr)
var P []int = make([]int, maxLen)
var center int = 0
var right int = 0
for i := 0; i < maxLen; i++ {
var mirror int = 2*center - i
if mirror < 0 {
mirror = 0
}
if right > i {
P[i] = P[mirror]
if P[mirror] > right-i {
P[i] = right - i
}
}
for i-P[i] >= 0 && i+P[i] < maxLen && expandStr[i-P[i]] == expandStr[i+P[i]] {
P[i]++
}
if i+P[i] > right {
center = i
right = i + P[i]
}
}
var maxIndex int = 0
for i, v := range P {
if v > P[maxIndex] {
maxIndex = i
}
}
var start int = (maxIndex - P[maxIndex] + 1) / 2
return s[start : start+P[maxIndex]-1]
}
``````

#### JavaScript

##### Expand Around Center
``````/**
* @param {string} s
* @return {string}
*/

var longestPalindrome = function (s) {
if (s.length === 0) return '';
else if (s === s.split('').reverse().join('')) return s;
let start = 0,
end = 0;
for (let i = 0; i < s.length; i++) {
const len1 = expandAroundCenter(s, i, i);
const len2 = expandAroundCenter(s, i, i + 1);
const length = Math.max(len1, len2);
if (length > end - start) {
start = i - Math.floor((length - 1) / 2);
end = i + Math.floor(length / 2);
}
}
return s.slice(start, end + 1);
};

const expandAroundCenter = (s, left, right) => {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
};
``````
##### Manacher's Algorithm
``````/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
if (!s || !s.length) return '';
const str = `#\${s.split('').join('#')}#`;
const n = str.length;
let center = 0,
const P = new Array(n).fill(0);

for (let i = 0; i < n; i++) {
P[i] = 1;
} else {
const i_mirror = 2 * center - i > 0 ? 2 * center - i : 0;
P[i] = Math.min(P[i_mirror], radius - i);
}
let lo = i - P[i],
hi = i + P[i];
while (lo >= 0 && hi < n && str[lo] === str[hi]) {
lo--, hi++;
}
P[i] = hi - i;

if (i + P[i] > radius) {
center = i;
}
}
const maxLen = Math.max(...P);
const centerIndex = P.indexOf(maxLen);
const res = str.substring(centerIndex - maxLen + 1, centerIndex + maxLen);
return res.split('#').join('');
};
``````

#### Kotlin

``````
``````

#### PHP

``````
``````

#### Python

##### Expand Around Center
``````class Solution:
def longestPalindrome(self, s: str) -> str:
if s == s[::-1]:
return s

start = end = 0
for i in range(len(s)):
len1 = self.expandAroundCenter(s, i, i)
len2 = self.expandAroundCenter(s, i, i + 1)
length = max(len1, len2)
if length > end - start:
start = i - (length - 1) // 2
end = i + length // 2

return s[start:end + 1]

def expandAroundCenter(self, s: str, left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1

return right - left - 1
``````
##### Manacher's Algorithm
``````class Solution:
def longestPalindrome(self, s: str) -> str:
T = '#'.join('^{}\$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range(1, n - 1):
P[i] = (R > i) and min(R - i, P[2 * C - i])
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1

if i + P[i] > R:
C, R = i, i + P[i]

max_len, center_idex = max((n, i) for i, n in enumerate(P))
return s[(center_idex - max_len) // 2: (center_idex + max_len) // 2]
``````

#### Rust

``````
``````

#### Swift

``````
``````