class Solution {
public:
int maxPalindromes(string s, int k) {
}
};
6236. 不重叠回文子字符串的最大数目
给你一个字符串 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 <= 2000s 仅由小写英文字母组成原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-08-07 16:09:58
func maxPalindromes(s string, k int) int {
n := len(s)
f := make([]int, n+1)
for i := 0; i < 2*n-1; i++ {
l, r := i/2, i/2+i%2 // 中心扩展法
f[l+1] = max(f[l+1], f[l])
for l >= 0 && r < n && s[l] == s[r] {
if r-l+1 >= k {
f[r+1] = max(f[r+1], f[l]+1)
break
}
l--
r++
}
}
return f[n]
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.3 MB, 提交时间: 2023-08-07 16:09:39
class Solution {
public:
int maxPalindromes(string s, int k) {
int n = s.length(), f[n + 1];
memset(f, 0, sizeof(f));
for (int i = 0; i < 2 * n - 1; ++i) {
int l = i / 2, r = l + i % 2; // 中心扩展法
f[l + 1] = 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] = max(f[r + 1], f[l] + 1);
break;
}
}
return f[n];
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 39.6 MB, 提交时间: 2023-08-07 16:09:21
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];
}
}
python3 解法, 执行用时: 64 ms, 内存消耗: 16.2 MB, 提交时间: 2023-08-07 16:09:04
'''
定义 f[i] 表示 s[0..i−1] 中的不重叠回文子字符串的最大数目。
特别地，定义 f[0]=0，方便我们表示空字符串。
分类讨论：
如果 s[i] 不在回文子串中，那么有 f[i+1]=f[i]。
如果 s[r] 在回文子串中，那么采用中心扩展法，当 s[l..r] 是回文子串，且 r−l+1≥k 时，
有状态转移方程 f[r+1]=max(f[r+1],f[l]+1 这两种情况取最大值。
最后答案为 f[n]，这里 n 为 s 的长度。
代码实现时，由于长度为 x 的回文子串一定包含长为 x−2 的回文子串，所以回文子串的长度达到 k 就可以退出循环了。
'''
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
n = len(s)
f = [0] * (n + 1)
for i in range(2 * n - 1):
l, r = i // 2, i // 2 + i % 2 # 中心扩展法
f[l + 1] = max(f[l + 1], f[l])
while l >= 0 and r < n and s[l] == s[r]:
if r - l + 1 >= k:
f[r + 1] = max(f[r + 1], f[l] + 1)
break
l -= 1
r += 1
return f[n]