题目:
给你一个字符串 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 仅由小写英文字母组成
java代码:
class Solution {
public int maxPalindromes(String S, int k) {
var s = S.toCharArray();
var n = s.length;
var f = new int[n + 1];
for (var i = 0; i < 2 * n - 1; ++i) {
int l = i / 2, r = l + i % 2; // 中心扩展法
f[l + 1] = Math.max(f[l + 1], f[l]);
for (; l >= 0 && r < n && s[l] == s[r]; --l, ++r)
if (r - l + 1 >= k) {
f[r + 1] = Math.max(f[r + 1], f[l] + 1);
break;
}
}
return f[n];
}
}
网友评论