题解 | #最长回文子串#

import java.util.Scanner;

/**
 * @author hll[yellowdradra@foxmail.com]
 * @description 最长回文子串
 * @date 2021-05-21 00:20
 **/
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = str.length();
        boolean[][] dp = new boolean[n][n];
        // 对角线值为true 即只包含单个字符的字符串肯定为回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        int max = Integer.MIN_VALUE;
        for (int r = 1; r < n; r++) {
            for (int l = 0; l < r; l++) {
                // 如果 r - l == 1 是 aa型 回文串
                // 如果 r - l == 2 是 aba型 回文串
                // 如果 [l + 1, r - 1] 是回文串 那么是 a*a型回文串  
                if (str.charAt(l) == str.charAt(r)
                        && (r - l < 3 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    max = Math.max(max, r - l + 1);
                }
            }
        }
        System.out.println(max);
    }
}