问题描述
给你一个字符串 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 仅由小写英文字母组成
问题求解
典型的线性dp,dp[i]表示以i-1结尾的最大数目,判断一下是否包含最后一个字符即可。
另外加入一个判断所有回文子串的模块。
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
n = len(s)
flag = [[0] * n for _ in range(n)]
def extend(s, l, r):
if l < 0 or r >= n or s[l] != s[r]: return
flag[l][r] = 1
extend(s, l - 1, r + 1)
for i in range(n):
extend(s, i, i)
extend(s, i, i + 1)
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1]
for j in range(i - k, -1, -1):
if flag[j][i - 1]:
dp[i] = max(dp[i], dp[j] + 1)
return dp[n]
标签:2472,extend,flag,range,DP,字符串,dp,回文
From: https://www.cnblogs.com/hyserendipity/p/16894425.html