题解 | #最长回文子串#注意边界

import java.util.*;

// 这个题感觉没法做到时间复杂度为O（n），当然也可能存在。看了另外一个兄弟的解法，空间复杂度降低到O（1），省略了dp数组，挺好！
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String raw = in.nextLine();
        int max = 0;
        //时间复杂度是O（n^2）,空间复杂度是O（n）
        boolean[] dp = new boolean[raw.length() / 2 + 1];
        dp[0] = true;
        if(raw.length()==1){
            max = 1;
        }
        for (int i = 0; i <raw.length()-1; i++) {
            if (raw.charAt(i) != raw.charAt(i + 1)) {
                for (int j = 1; j < raw.length() / 2 + 1; j++) {
                    if (i + j > raw.length()-1 || i - j < 0) {
                        dp[j] = false;
                    }else{
                        dp[j] = dp[j - 1] && raw.charAt(i + j) == raw.charAt(i - j);
                    }
                }
                int m = dp.length-1;
                while (m >= 0) {
                    if (dp[m] == true) {
                        max = Math.max(max, m*2+1);
                        break;
                    }
                    m--;
                }
            } else {
                for (int j = 1; j < raw.length() / 2 + 1; j++) {
                    if (i + 1 + j > raw.length()-1 || i - j < 0) {
                        dp[j] = false;
                    }else{
                        dp[j] = dp[j - 1] && raw.charAt(i + 1 + j) == raw.charAt(i - j);
                    }
                    int m = dp.length-1;
                    while (m >= 0) {
                        if (dp[m] == true) {
                            max = Math.max(max, m*2+2);
                            break;
                        }
                        m--;
                    }
                }
            }
        }
        System.out.println(max);
        // 时间复杂度是O（n）,空间复杂度是O（2^n）
        // int maxFinal = 0;
        // for (int i = 0; i < raw.length(); i++) {
        //     max = Math.max(judgePalindrome1(raw, i, i) + 1, judgePalindrome2(raw, i, i)+1);
        //     maxFinal = Math.max(max, maxFinal);
        // }
        // System.out.println(maxFinal);
    }
    // public static int judgePalindrome1(String raw, int left, int right) {
    //     int num = 0;
    //     if (--left >= 0 && ++right <= raw.length() - 1) {
    //         if (raw.charAt(left) == raw.charAt(right)) {
    //             num =  2 + Math.max(judgePalindrome1(raw, left, right), judgePalindrome2(raw,
    //                                 left, right));
    //         }
    //     }
    //     return num;
    // }
    // public static int judgePalindrome2(String raw, int left, int right) {
    //     int num = 0;
    //     int right1 = right + 1;
    //     int right2 = right + right - left + 1;
    //     if (right2 < raw.length() - 1) {
    //         if (raw.substring(left, right + 1).equals(raw.substring(right1, right2 + 1))) {
    //             num = right - left + 1 + Math.max(judgePalindrome1(raw, left, right2),
    //                                               judgePalindrome2(raw, left, right2));
    //         }
    //     } else if (right2 == raw.length() - 1) {
    //         if (raw.substring(left, right + 1).equals(raw.substring(right1))) {
    //             num = right - left + 1 + Math.max(judgePalindrome1(raw, left, right2),
    //                                               judgePalindrome2(raw, left, right2));
    //         }
    //     }
    //     return num;
    // }
}