这道题是 LeetCode 2472 不重叠回文子字符串的最大数目要求从字符串中选出尽可能多的不重叠回文子串每个长度至少为 k。解题思路核心是动态规划 中心扩展法1. 定义 dp[i] 表示 s[0..i-1] 中能选出的最大数目2. 对于每个位置 i有两种选择- 不选 s[i-1]dp[i] dp[i-1]- 选以某个位置结尾的回文串需要找到所有以 i-1 结尾且长度 ≥ k 的回文串Java 实现class Solution {public int maxPalindromes(String s, int k) {int n s.length();int[] dp new int[n 1];// 中心扩展法枚举所有可能的回文串for (int center 0; center 2 * n - 1; center) {int left center / 2;int right left center % 2;// 先处理不选当前字符的情况dp[left 1] Math.max(dp[left 1], dp[left]);// 向两边扩展寻找回文串while (left 0 right n s.charAt(left) s.charAt(right)) {int len right - left 1;if (len k) {// 找到长度 ≥ k 的回文串更新 dpdp[right 1] Math.max(dp[right 1], dp[left] 1);break; // 贪心找到第一个长度 ≥ k 的就停止}left--;right;}}return dp[n];}}另一种实现更直观的 DP 预处理class Solution {public int maxPalindromes(String s, int k) {int n s.length();// dp[i] 表示 s[0..i-1] 的最大数目int[] dp new int[n 1];// 预处理所有回文串boolean[][] isPalindrome new boolean[n][n];for (int i n - 1; i 0; i--) {for (int j i; j n; j) {if (s.charAt(i) s.charAt(j)) {if (j - i 2) {isPalindrome[i][j] true;} else {isPalindrome[i][j] isPalindrome[i 1][j - 1];}}}}// DPfor (int i 1; i n; i) {dp[i] dp[i - 1]; // 不选 s[i-1]// 枚举以 i-1 结尾的回文串for (int j i - k; j 0; j--) {if (isPalindrome[j][i - 1]) {dp[i] Math.max(dp[i], dp[j] 1);break; // 贪心优化找到第一个就停止}}}return dp[n];}}贪心优化的解释为什么找到第一个长度 ≥ k 的回文串就可以停止因为如果有一个更长的回文串 s[l..r]长度 k它一定包含一个更短的回文串 s[l1..r-1]长度 ≥ k-2。选择更短的回文串可以留出更多空间给其他回文串不会使结果更差。示例验证示例 1s abaccdbbd, k 3输出2解释选择 aba 和 dbbd示例 2s adbcda, k 2输出0解释不存在长度 ≥ 2 的回文串复杂度分析- 时间复杂度O(n²)中心扩展法或预处理回文串- 空间复杂度O(n)dp 数组优化版本马拉车算法如果需要 O(n) 的时间复杂度可以使用 Manacher 算法预处理所有回文串class Solution {public int maxPalindromes(String s, int k) {int n s.length();int[] dp new int[n 1];// Manacher 算法预处理// ... (实现马拉车)// 然后进行 DPfor (int i 1; i n; i) {dp[i] dp[i - 1];// 检查以 i-1 结尾的长度为 k 或 k1 的回文串if (i k isPalindrome[i - k][i - 1]) {dp[i] Math.max(dp[i], dp[i - k] 1);}if (i k 1 isPalindrome[i - k - 1][i - 1]) {dp[i] Math.max(dp[i], dp[i - k - 1] 1);}}return dp[n];}}这个优化版本利用了只需检查长度为 k 和 k1 的回文串的性质进一步优化了效率。