题解 | #密码截取#

// mark mark mark

// 方法1. 暴力求解（超时）：头尾双指针 判断字串是否回文
// 方法2. 动态规划 dp[i][j] 从a[i]到a[j]的字串是否是回文字串 boolean值
// 状态转移方程：a[i] == a[j] && (a[i + 1][j - 1] || j - i <= 2) 
//                      -> dp[i][j] = true;
// 初始条件：dp[i][i] = true

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            int length = s.length();
            int ans = 0;
            boolean dp[][] = new boolean[length + 1][length + 1];
            for (int i = 1; i < length + 1; i++) {
                // 长度为一的字符串肯定是回文子串
                dp[i][i] = true;
            }
            for (int i = 2; i < length + 1; i++) {
                // j < i
                for (int j = 1; j < i; j++) {
                    if (s.charAt(j - 1) == s.charAt(i - 1) && 
                        (dp[j + 1][i - 1] || i - j <= 2)) {
                            dp[j][i] = true;
                            ans = Math.max(ans, i - j + 1);
                        }
                }
            }
            System.out.println(ans);
        }
    }
}