/**
 * @Author :田宇寒.
 * @Date :Created in 16:27 2021年5月31日
 * @Description:最长回文数串
 * @Modified By:
 * @Version: 1.0$
 */
public class code5 {

 public static void main(String[] args) {
 Solution2 solution = new Solution2();
 System.out.println(solution.longestPalindrome("bb"));
 }

 static class Solution {
 public String longestPalindrome(String s) {
 /**
 * create by: 田宇寒
 * description: 中心扩散算法 时间复杂度O(N2) 空间复杂度O(1)
 * create time: 14:41 2021年6月2日
 * @Param: s
 * @return java.lang.String
 */
 if (s.length() == 1) {
 return s;
 }
 char[] chars = s.toCharArray();
 int length = chars.length;
 int maxLength=0, left, right, leftIndex = 0, rightIndex = 0;
 for (int i = 0; i < length - 1; i++) {
 left = right = i;
 while (right < length && chars[right] == chars[i]) {
 ++right;
 }
 while (true) {
 if (left - 1 < 0 || right ==length || chars[left - 1] != chars[right]) {
 if (right - left >= maxLength) {
 leftIndex = left;
 rightIndex = right;
 maxLength = right - left;
 }
 break;
 }
 --left;
 ++right;
 }
 }
 return s.substring(leftIndex, rightIndex);
 }
 }

 static class Solution2 {
 public String longestPalindrome(String s) {
 /**
 * create by: 田宇寒
 * description: 动态规划 时间复杂度O(N2) 空间复杂度O(N2)
 * create time: 16:48 2021年6月2日
 * @Param: s
 * @return java.lang.String
 */
 if (s.length() == 1) {
 return s;
 }
 char[] chars = s.toCharArray();
 int length = chars.length;
 int begin = 0;
 int maxLength = 0;
 boolean d[][] = new boolean[length][length];
 for (int i = 0 ; i < length; i++) {
 d[i][i] = true;
 }

 for (int j = 1 ; j < length; j ++) {
 for (int i = 0; i < j; i++) {
 if (chars[i] != chars[j]) {
 d[i][j] = false;
 } else {
 if (j - i < 3) {
 d[i][j] = true;
 } else {
 d[i][j] = d[i+1][j-1];
 }
 }
 if (d[i][j] && j - i + 1>= maxLength) {
 begin = i;
 maxLength = j - i + 1;
 }
 }
 }
 return s.substring(begin, begin + maxLength);
 }
 }
}