描述

输入描述：

输入一个字符串（字符串的长度不超过2500）

输出描述：

返回有效密码串的最大长度

示例

输入：ABBA
输出：4

知识点：字符串，指针，动态规划

难度：⭐⭐⭐

题解

方法一：中心扩散法

图解：

解题思路：

最长回文子串的中心扩散法，遍历每个字符作为中间位，进行左右比较

算法流程：

• 从右到左，对每个字符进行遍历处理，并且每个字符要处理两次，因为回文子串有两种情况：
  • ABA型：只需要从当前字符向两边扩散，比较左右字符是否相等，找出以当前字符为中心的最长回文子串长度
  • ABBA型：只需要从当前字符和下一个字符向两边扩散，比较左右字符是否相等，找出以当前字符和下一个字符为中心的最长回文子串长度
• 最后比对两种类型的长度，取自较长的长度

Java 版本代码如下：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(solution(s));
    }
    
    private static int solution(String s) {
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            // ABA型
            int len1 = longest(s, i, i);
            // ABBA型
            int len2 = longest(s, i, i + 1);
            res = Math.max(res, len1 > len2 ? len1 : len2);
        }
        return res;
    }
    
    private static int longest(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

复杂度分析：

时间复杂度：$O(N^2)O(N^2)$，需要遍历每个字符，复杂度为 O(N)，对于每个字符的处理也需要 O(N) 的复杂度，因此总的时间复杂度为 O(N^2)

空间复杂度：$O(1)O(1)$，只用到左右双指针，无需额外空间

方法二：动态规划

解题思路：

对于最值问题，往往可以采用动态规划思想降低时间复杂度和状态压缩，采用空间换时间的思想

算法流程：

• 确定状态：对比的两个字符索引起始和终止索引位置

• 定义 dp 数组：字符串s的 i 到 j 索引位置的字符组成的子串是否为回文子串

• 状态转移: 如果左右两字符相等, 同时[l+1...r-1]范围内的字符是回文子串, 则 [l...r] 也是回文子串

• 状态转移的同时，不断更新对比的子串长度，最终确定最长回文子串的长度

Java 版本代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        while ((s = br.readLine()) != null) {
            System.out.println(validLen(s));
        }
        br.close();
    }

    public static int validLen(String s) {
        int len = s.length();
        // 状态：对比的两个字符索引起始和终止索引位置
        // 定义: 字符串s的i到j字符组成的子串是否为回文子串
        boolean[][] dp = new boolean[len][len];
        int res = 0;
        // base case
        for(int i = 0; i < len - 1; i++) {
            dp[i][i] = true;
        }

        for(int r = 1; r < len; r++) {
            for(int l = 0; l < r; l++) {
                // 状态转移：如果左右两字符相等,同时[l+1...r-1]范围内的字符是回文子串
                // 则 [l...r] 也是回文子串
                if(s.charAt(l) == s.charAt(r) && (r-l <= 2 || dp[l+1][r-1])) {
                    dp[l][r] = true;
                    // 不断更新最大长度
                    res = Math.max(res, r - l + 1);
                } 
            }
        }
        return res;
    }
}

复杂度分析：

时间复杂度：$O(N^2)O(N^2)$， 状态转移时，子问题个数为 N ^ 2, 子问题处理时间复杂度为 O(1)，因此总的时间复杂度为 O(N^2)

空间复杂度：$O(N^2)O(N^2)$，定义了一个二维数组，用户保存状态