目标
给你一个字符串 s 和一个 正 整数 k 。
从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：
- 每个子字符串的长度 至少 为 k 。
- 每个子字符串是一个 回文串 。
返回最优方案中能选择的子字符串的 最大 数目。
子字符串 是字符串中一个连续的字符序列。
示例 1 ：
输入：s = "abaccdbbd", k = 3
输出：2
解释：可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。示例 2 ：
输入：s = "adbcda", k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。说明：
- 1 <= k <= s.length <= 2000
- s 仅由小写英文字母组成
思路
返回字符串 s 中长度 至少 为 k 的不重叠回文子串的最大个数。
定义 dp[i] 表示 s[i, n - 1] 中长度为 k 的不重叠回文子串的最大数目，
- 如果不选
s[i]，dp[i] = dp[i + 1] - 如果选择
s[i]，枚举终点j，使得j - i + 1 >= k，如果s[i, j]是回文，dp[i] = max(dp[i], 1 + dp[j + 1]))
需要快速判断子串是否是回文，可以预处理。
代码
/**
* @date 2026-09-15 9:24
*/
public class MaxPalindromes2472 {
public int maxPalindromes(String s, int k) {
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
int l = i - 1, r = i + 1;
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
isPalindrome[l--][r++] = true;
}
l = i - 1;
r = i;
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
isPalindrome[l--][r++] = true;
}
}
int[] dp = new int[n + 1];
for (int i = n - k; i >= 0; i--) {
dp[i] = dp[i + 1];
for (int j = n - 1; j >= i + k - 1; j--) {
if (isPalindrome[i][j]) {
dp[i] = Math.max(dp[i], 1 + dp[j + 1]);
}
}
}
return dp[0];
}
}
性能
