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

# 5.Longest-Palindromic-Substring

## 5. Longest Palindromic Substring

## 题目地址

<https://leetcode.com/problems/longest-palindromic-substring/>

## 题目描述

```
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"
```

## 代码

### Approach 1: Brute Force

穷举所有的子串，O(Cn^2) = O(n^2), 每次判断字符串是否为回文，复杂度为 *O*(*n*), 故总的时间复杂度为 O(n^3), 大数据集下可能 [TLE](https://algorithm.yuanbin.me/zh-hans/GLOSSARY.html#tle). 仅在最后返回取子串，空间复杂度为 O(1). P.S. 目前仅 Java 对回文判断优化过。

```java
class Solution {
    public String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) return "";

    int sLen = s.length();
    int longest = 0, left = 0;
    for (int i = 0; i < sLen; i++) {
      for (int j = i; j < sLen; j++) {
        if (isPalindrome(s, i, j) && j - i + 1 > longest) {
          longest = j - i + 1;
          left = i;
        }
      }
    }

    return s.substring(left, left + longest);
  }

  private boolean isPalindrome(String s, int left, int right) {
    for (int i = left, j = right; i <= j; i++, j--) {
      if (s.charAt(i) != s.charAt(j))    return false;
    }

    return true;
  }
}
```

### Approach #2 odd + even

```java
class Solution {
  public String longestPalindrome(String s) {
    if (s == null || s.isEmpty())    return "";

    int sLen = s.length();
    int longest = 0, left = 0;
    for (int i = 0; i < sLen; i++) {
      // odd
      int leftIndex = leftPalindromeIndex(s, i, i);
      int palindromeLen = 2 * (i - leftIndex) + 1;
      if (palindromeLen > longest) {
        left = leftIndex;
        longest = palindromeLen;
      }

      // even
      leftIndex = leftPalindromeIndex(s, i, i + 1)；
      palindromeLen = 2 * (i - leftIndex + 1);
      if (palindromeLen > longest) {
        left = leftIndex;
        longest = palindromeLen;
      }
    }

    return s.substring(left, left + longest);
  }

  private int leftPalindromeIndex(String s, int left, int right) {
    for (; left >= 0 && right < s.length(); left--, right++) {
      if (s.charAt(left) != s.charAt(right)) break;
    }
    return left + 1;
  }

}
```