> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/01_two_pointers/5.-longest-palindromic-substring.md).

# 5. 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](/mle-interview/01_leetcode/01_two_pointers/647.-palindromic-substrings.md)

[131. Palindrome Partitioning](/mle-interview/01_leetcode/07_dfs/131.-palindrome-partitioning.md)

[132. Palindrome Partitioning II](/mle-interview/01_leetcode/09_dynamic_program/132.-palindrome-partitioning-ii.md)

[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](/mle-interview/01_leetcode/09_dynamic_program/1216.-valid-palindrome-iii.md)

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

[Count of Palindromic Substrings](/mle-interview/01_leetcode/01_two_pointers/5.-longest-palindromic-substring.md)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/01_two_pointers/5.-longest-palindromic-substring.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.