给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
回文子串，呜呜呜，大一开始就被这题折磨，虐我千百遍，呆它如初恋！
暴力双循环别想了，直接上优化方案把，动态规划还没看，先来个，中心拓展算法，思路很简单，从中间往两边扩散，如果两边相等，那么就是回文，最后记录长度，然后截取就可以了，思路就是这么个思路，下面是具体分析：
首先定义 begin，记录开始截取的位置，定义 maxLen，记录最长回文子串的长度，便于 substring 进行截取，循环 s 字符串，由于回文子串分为奇数回文（aba）和偶数回文 （abba），所以都要进行求长度，取其中最大的长度，进行截取，如果当前比之前的大，更新，截取，截取的思路是这样的，当前的回文子串长度是 maxLen，那么一半就是 maxLen - 1 然后除以 2，能够得到一半的长度，再让 i 减去，就能得到起始位置。
class Solution {
public String longestPalindrome(String s) {
int begin = 0;
int maxLen = Integer.MIN_VALUE;
for (int i = 0; i < s.length(); i++) {
int left = maxStringLength(s, i, i);
int right = maxStringLength(s, i, i + 1);
int curMaxLen = Math.max(left, right);
if (maxLen < curMaxLen) {
maxLen = curMaxLen;
begin = i - (maxLen - 1) / 2;
}
}
return s.substring(begin, begin + maxLen);
}
public int maxStringLength(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return j - i - 1;
}
}
双指针可能也不是终点，动态规划才是 yyds，动态分析：定义一个 二维的 dp 数组，横纵坐标就是字符串的范围，如果是就是 true，不是就是 false，有几种情况一定是回文：
i 和 j 位置的元素相同时：
1、j - i 的长度等于 0，说明 j 和 i 重合，比如 a，一定是回文，
2、j - i 的长度等于 1，说明 j 和 i 相等，比如 aa，一定是回文
3、dp[i + 1][j - 1] 也是回文时，外面的俩也相等，比如 a bab a，此时内芯是 bab 是回文，同时外面都是 a 还相等
class Solution {
public String longestPalindrome(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int maxLen = Integer.MIN_VALUE;
int left = 0;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i <= 1) {
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) {
dp[i][j] = true;
}
}
// 如果是 回文，判断是否需要更新
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
left = i;
}
}
}
return s.substring(left, left + maxLen);
}
}