# 5. Longest Palindromic Substring

[https://leetcode.com/problems/longest-palindromic-substring/](https://leetcode.com/problems/longest-palindromic-substring/)

## solution

* 双指针

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = 0
        l = r = 0
        for i in range(len(s)):
            length, left ,right = self.pali(s, i, i)  # 这个写法有点繁杂，只需要返回一个子串，然后选择最长的即可
            if length > longest:
                longest = length
                l = left
                r = right

            length, left, right = self.pali(s, i, i+1)
            if length > longest:
                longest = length
                l = left
                r = right
        return s[l:r+1]

    def pali(self, s, l, r):
        temp_length = 0
        while l >=0 and r < len(s) and s[l] == s[r]:
            if l == r:
                temp_length += 1
            else:
                temp_length += 2
            l -= 1
            r += 1
        return temp_length, l+1, r-1
```

时间复杂度：O()\
空间复杂度：O()

* 动态规划

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        # dp[i][j]: 字符串s[i:j]是否为回文. 虽然目前是最长, 但状态用了是否同时记录起点和长度
        dp = [[True] * n for _ in range(n)]

        start = 0
        res = 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = False

                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    if res < j - i + 1:
                        start = i
                        res = j - i + 1
        return s[start: start + res]
```

## follow up-回文类

[516. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/description/)

```python
# 动态规划
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # dp[i][j]: 字符串s[i:j]子字符最长回文
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1

        for i in range(len(s)-1, -1, -1):  # 注意顺序
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][-1]
```

时间复杂度：O(n^2)\
空间复杂度：O(n^2)

[647. Palindromic Substrings](647.-palindromic-substrings)

[131. Palindrome Partitioning](../07_dfs/131.-palindrome-partitioning)

[132. Palindrome Partitioning II](../09_dynamic_program/132.-palindrome-partitioning-ii)

[2193. Minimum Number of Moves to Make Palindrome](https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/)

```python
```

[336. Palindrome Pairs](https://leetcode.com/problems/palindrome-pairs/description/)

```python
```

[680. Valid Palindrome II](https://leetcode.com/problems/valid-palindrome-ii/description/)

```python
# follow up: 移除最多k个, -> 1216

class Solution:
    def valid_palindrome(self, s: str) -> bool:
        l = 0
        r = len(s) - 1

        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                # 关键是这里: 构建一个判断字符串s从l到r位置是否回文的辅助函数
                return self.is_valid(s, l+1, r) or self.is_valid(s, l, r-1)
        return True

    def is_valid(self, s, l, r):
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                return False
        return True
```

时间复杂度：O(n)\
空间复杂度：O(1)

* 超时

```python
class Solution:
    def validPalindrome(self, s: str) -> bool:
        if self.is_valid(s):
            return True

        for i in range(len(s)):
            if self.is_valid(s[:i] + s[i+1:]):
                return True
        return False

    def is_valid(self, s):
        l = 0
        r = len(s) - 1
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True
```

[1216 Valid Palindrome III](../09_dynamic_program/1216.-valid-palindrome-iii)

[1930. Unique Length-3 Palindromic Subsequences](https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/)

[Count of Palindromic Substrings](5.-longest-palindromic-substring)
