1. 题目链接：https://leetcode.cn/problems/longest-palindromic-substring/

    2. 方法签名

      1. public String longestPalindrome(String s);

    3. 测试用例

      1. // 单字符
      2. Assert.assertEquals("a", longestPalindrome("a"));
      3. // 子串满足回文
      4. Assert.assertEquals("bab", longestPalindrome("babad"));
      5. // 偶数长度的回文子串
      6. Assert.assertEquals("abccba", longestPalindrome("abccba"));
      7. // 奇数长度的回文子串
      8. Assert.assertEquals("abcdcba", longestPalindrome("abcdcba"));

    4. 方法一：朴素解法

    两层 for 循环遍历字符串 S，判断 S[i:j] 如果是回文子串且大于当前最长回文子串长度，更新开始下标 start 和 最大长度 maxLen。

    1. public String longestPalindrome(String s) {
    2.     int n = s.length();
    3.     int start = 0;
    4.     int maxLen = 1;
    5.     char[] chars = s.toCharArray();
    6.     for (int i = 0; i < n; i++) {
    7.         for (int j = i; j < n; j++) {
    8.             if (maxLen < (j - i + 1) && checkPalindrome(chars, i, j)) {
    9.                 start = i;
    10.                 maxLen = j - i + 1;
    11.             }
    12.         }
    13.     }
    14.     return s.substring(start, start + maxLen);
    15. }
    17. private boolean checkPalindrome(char[] chars, int i, int j) {
    18.     while (i < j && chars[i] == chars[j]) {
    19.         i++;
    20.         j--;
    21.     }
    22.     return i >= j;
    23. }
    1. 方法二：动态规划

    对于一个长度大于2的回文子串，将它首位两个字母去掉后 得到的子串仍是回文子串。例如对于 “cbabc” 去掉收尾字母后 “bab” 仍是回文子串。
    根据这样的思路 我们可以使用动态规划解决问题。我们用 P(i,j) 表示子串S[i:j] 是否回文：

    • P(i,j) 等于 true ，如果 Si…Sj 是回文串
    • P(i,j) 等于 false，其他情况 如s[i,j] 不是一个回文串 或 i > j 不构成子串

    那么我们就可以写出动态规划的状态转移方程：
    最长回文子串 - 图1
    也就是说只有 s[i + 1 : j - 1] 是回文串，并且s的第i个字母和第j个字母相同时，s[i,j] 才会是回文串。
    以上所有讨论建立在字符串长度 > 2 的前提上，我们还需要考虑边界情况 len ≤ 2。对于长度等于1 的字符串，显然它是回文串。长度等于2的字符串 只要它两个字母相同 也是回文串。因此我们可以写出动态规划的边界条件：
    最长回文子串 - 图2

    1. public String longestPalindrome(String s) {
    2.     if (s == null || s.length() < 2) {
    3.         return s;
    4.     }
    6.     int start = 0;
    7.     int maxLen = 1;
    8.     int n = s.length();
    10.     boolean[][] dp = new boolean[n][n];
    11.     for (int i = 0; i < n; i++) {
    12.         dp[i][i] = true;
    13.     }
    14.     char[] chars = s.toCharArray();
    16.     for (int len = 2; len <= n; ++len) {
    17.         for (int i = 0; i < n; i++) {
    18.             int j = i + len - 1;
    19.             if (j == n) {
    20.                 break;
    21.             }
    22.             if (chars[i] != chars[j]) {
    23.                 dp[i][j] = false;
    24.             } else {
    25.                 if (len < 3) {
    26.                     dp[i][j] = true;
    27.                 } else {
    28.                     dp[i][j] = dp[i+1][j-1];
    29.                 }
    30.             }
    32.             if (dp[i][j] && len > maxLen) {
    33.                 start = i;
    34.                 maxLen = len;
    35.             }
    36.         }
    37.     }
    38.     return s.substring(start, start + maxLen);
    39. }
    1. 方法三：中心扩展算法

    我们也可以从回文中心出发 如果首尾字母相同向两边扩展，直到当前不是回文子串或遍历完毕。比如 “cbaabc” 可以从中心 “aa” 向两边扩展得到最长回文子串它自己。
    回文串中心所在下标 取决于回文串长度的奇偶性，以奇数长度 “cbabc” 和偶数长度 “cbaabc” 举例分析：

    • “cbabc”长度等于5 ，回文中心是 s[2] ，回文串左边界 left = 2 - (5-1)/2 = 0
    • “cbaabc”长度等于6，回文中心是 s[2] 和 s[3]，回文串左边界 left = 2 - (6-1)/2 = 0

    通过举例分析 在知道回文串长度 len 和 左回文中心 i 的情况下，左边界 left = i - (len-1)/2

    1. public String longestPalindrome_expandAroundCentral(String s) {
    2.     if (s == null || s.length() < 2) {
    3.         return s;
    4.     }
    6.     int start = 0;
    7.     int maxLen = 1;
    8.     char[] chars = s.toCharArray();
    10.     for (int i = 0; i < chars.length; i++) {
    11.         int len1 = expandAroundCentral(chars, i, i);
    12.         int len2 = expandAroundCentral(chars, i, i+1);
    13.         int len = Math.max(len1, len2);
    14.         if (len > maxLen) {
    15.             start = i - (len-1)/2;
    16.             maxLen = len;
    17.         }
    18.     }
    19.     return s.substring(start, start + maxLen);
    20. }
    22. private int expandAroundCentral(char[] chars, int left, int right) {
    23.     while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
    24.         left--;
    25.         right++;
    26.     }
    27.     return right-left-1;
    28. }