2472-不重叠回文子字符串的最大数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

  • 每个子字符串的长度 至少 为 k 。
  • 每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

示例 1 ：

**输入：** s = "abaccdbbd", k = 3
**输出：** 2
**解释：** 可以选择 s = " _ **aba**_ cc _ **dbbd**_ " 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。

示例 2 ：

**输入：** s = "adbcda", k = 2
**输出：** 0
**解释：** 字符串中不存在长度至少为 2 的回文子字符串。

提示：

  • 1 <= k <= s.length <= 2000
  • s 仅由小写英文字母组成

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

计算每个子串是否回文，可以用中心扩展法，思路参考 647. 回文子串 的 官方题解 ，下面只讲解 DP 部分。

定义 f[i] 表示 s[0..i-1] 中的不重叠回文子字符串的最大数目。

特别地，定义 f[0] = 0，方便我们表示空字符串。

分类讨论：

  • 如果 s[i] 不在回文子串中，那么有 f[i+1] = f[i]。
  • 如果 s[r] 在回文子串中，那么采用中心扩展法，当 s[l..r] 是回文子串，且 r-l+1\ge k 时，有状态转移方程

f[r+1] = \max(f[r+1], f[l]+1)

这两种情况取最大值。

最后答案为 f[n]，这里 n 为 s 的长度。

代码实现时，由于长度为 x 的回文子串一定包含长为 x-2 的回文子串，所以回文子串的长度达到 k 就可以退出循环了。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 }

复杂度分析

  • 时间复杂度：O(nk)，其中 n 为 s 的长度。
  • 空间复杂度：O(n)。

相似题目

 Comments
On this page
2472-不重叠回文子字符串的最大数目