难度: Hard
给你一个字符串 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 仅由小写英文字母组成运行时间: 43 ms
内存: 16.1 MB
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 = i // 2
r = 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]
这个题解采用了动态规划的方法与中心扩展算法的结合。对于每个中心点（字符或两字符之间），算法尝试向两边扩展以找到可能的回文串。动态规划数组 `f` 中，`f[i]` 表示考虑到字符串的前 `i` 个字符，能够形成的最大不重叠的回文串个数。每次找到一个合法的回文串后（长度至少为 `k`），就尝试更新 `f[r+1]`（即扩展到的右边界的下一个位置）。这样，当遍历完成所有可能的中心点后，`f[n]` 将包含整个字符串的最大不重叠回文子字符串数目。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
n = len(s)
f = [0] * (n + 1) # 动态规划数组，f[i] 表示前i个字符的最大不重叠回文子串数
for i in range(2*n-1):
l = i // 2 # 确定中心点左侧
r = 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] # 返回整个字符串的最大不重叠回文子串数
在找到一个长度至少为k的回文串后，break的原因是为了避免重叠的情况。一旦找到满足条件的回文字符串，如果继续扩展可能会导致与其他已经确认的回文串重叠，从而违反题目的不重叠条件。因此，在找到第一个满足条件的回文串后，就立即停止扩展，确保此后每次更新的回文子串都是不重叠的。
在动态规划数组f中，初始化f[l+1]为max(f[l+1], f[l])的作用是保证f数组的单调性和正确性。这样的初始化确保了在考虑前l个字符的基础上，到第l+1个字符时，最大不重叠回文子字符串的数量至少不会减少。这种方式可以有效地继承前一个状态的值，确保不会因为后续操作而错过之前已经得到的最优解。
在动态规划解法中，确保更新的回文子串不重叠的机制是通过仔细控制数组f的更新逻辑来实现的。每次在找到一个合法的回文串后，更新f[r+1]（即回文串右边界的下一个位置）为max(f[r+1], f[l] + 1)。这样的更新方式确保了在第l个字符之前的最大不重叠回文串数加上当前新找到的回文串，而更新的位置r+1表示从下一个位置开始重新计算，避免了与当前回文串的重叠。
在中心扩展算法中，选择2n-1个中心点是为了覆盖所有可能的回文中心，包括字符本身和两个字符之间的位置。对于偶数长度的回文串，中心点位于两个字符之间；对于奇数长度的回文串，中心点位于某个字符上。具体地，中心点的计算公式为i // 2来确定中心点左侧l，而中心点右侧r则由i // 2 + i % 2确定。这样的设置可以确保每个可能的回文中心都被考虑到，从而不遗漏任何一个回文串的可能性。