给你一个字符串 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
仅由小写英文字母组成
方法一:预处理 + 记忆化搜索
预处理字符串
然后定义函数
时间复杂度
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
@cache
def dfs(i):
if i >= n:
return 0
ans = dfs(i + 1)
for j in range(i + k - 1, n):
if dp[i][j]:
ans = max(ans, 1 + dfs(j + 1))
return ans
n = len(s)
dp = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
ans = dfs(0)
dfs.cache_clear()
return ans
class Solution {
private boolean[][] dp;
private int[] f;
private String s;
private int n;
private int k;
public int maxPalindromes(String s, int k) {
n = s.length();
f = new int[n];
this.s = s;
this.k = k;
dp = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(dp[i], true);
f[i] = -1;
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
}
}
return dfs(0);
}
private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
int ans = dfs(i + 1);
for (int j = i + k - 1; j < n; ++j) {
if (dp[i][j]) {
ans = Math.max(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
}
}
class Solution {
public:
int maxPalindromes(string s, int k) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, true));
vector<int> f(n, -1);
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
}
}
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) return 0;
if (f[i] != -1) return f[i];
int ans = dfs(i + 1);
for (int j = i + k - 1; j < n; ++j) {
if (dp[i][j]) {
ans = max(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
};
return dfs(0);
}
};
func maxPalindromes(s string, k int) int {
n := len(s)
dp := make([][]bool, n)
f := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
f[i] = -1
for j := 0; j < n; j++ {
dp[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
}
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != -1 {
return f[i]
}
ans := dfs(i + 1)
for j := i + k - 1; j < n; j++ {
if dp[i][j] {
ans = max(ans, 1+dfs(j+1))
}
}
f[i] = ans
return ans
}
return dfs(0)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}