# LeetCode Solution, Medium, 5. Longest Palindromic Substring

# [5. Longest Palindromic Substring](https://leetcode.com/problems/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?

### 題目翻譯

提供一個字串 `s`，從中找出最長的回文子字串。有沒有可能利用先前的條件，讓時間複雜度變成 `O(n)` 呢？

## 解法解析

這題如果不考慮將時間複雜度降到 `O(n)` 的話難度的確只有 Medium 吧，但是一但考量到複雜度整個就是 Hard 等級了，因為就會需要使用到所謂的[馬拉車算法 (Manacher's Algorithm)](https://www.wikiwand.com/en/Longest_palindromic_substring#/Manacher's_algorithm)。如果不考慮的話，大多就會使用了中心擴展法來解個題目。

### 解法範例

#### Go

##### Expand Around Center

```go
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

```go
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

```javascript
/**
 * @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

```javascript
/**
 * @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,
        radius = 0;
    const P = new Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        if (i > radius) {
            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;
            radius = i + P[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

```kotlin
```

#### PHP

```php
```

#### Python

##### Expand Around Center

```python
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

```python
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

```rust
```

#### Swift

```swift
```

## Reference

- [老司机开车，教会女朋友什么是「马拉车算法」](https://www.cxyxiaowu.com/2665.html)
- [漫画：如何找到字符串中的最长回文子串？](https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485998&idx=1&sn=ecccf562324dac313a23964325145c78&chksm=fa0e65afcd79ecb9058babb2310f019e0ed5e5822503cce6a0d734d4fe2306b696d706f0bad8&scene=21#wechat_redirect)
- [longest palindromic substring 演算法整理 (Manacher’s algorithm)](https://cppext.com/?p=1743)
- [LeetCode - Longest Palindromic Substring](https://josephjsf2.github.io/data/structure/and/algorithm/2020/10/10/manacher-algorithm.html)