2472：不重叠回文子字符串的最大数目（2013 分）

Ian

2022-11-13 约 653 字预计阅读 2 分钟次阅读

力扣第 319 场周赛第 4 题

题目

给你一个字符串 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 仅由小写英文字母组成

相似问题：

分析

#1

令 f(i) 代表 s[:i] 的最大数目，容易写出递推式
- f(i) = max(f(i-1),1+max(f(j) for j in range(i) if i-j>=k and s[j:i] 回文))
注意到>=k+2 的子串无意义，只需要枚举 j=i-k 和 j=i-k-1 即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        f = [0]*(n+1)
        for i in range(k,n+1):
            f[i] = f[i-1]
            for j in [i-k,i-k-1]:
                if j>=0 and s[j:i]==s[j:i][::-1] and 1+f[j]>f[i]:
                    f[i] = 1+f[j]
        return f[-1]

19 ms

#2

判断区间是否回文还可以用 manacher 预处理

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


def manacher(s):
	n = len(s)
	A, B = [], [1]*n
	mid, r = 0, 0
	for i in range(n):
		a = min(A[2*mid-i], r-i) if r>i else 0
		while i-a and i+a<n-1 and s[i-a-1]==s[i+a+1]:
			a += 1
			B[i+a] = max(B[i+a],a*2+1)
		A.append(a)
		if i+a>r:
			mid, r = i, i+a
	return A,B       # A[i]:i为中心的臂长,B[i]:i结尾的最大回文子串长度（奇数）

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        def check(l,r):
            return A[l+r+1]>=r-l
        n = len(s)
        A,_ = manacher('#'+'#'.join(s)+'#')
        f = [0]*(n+1)
        for i in range(k,n+1):
            f[i] = f[i-1]
            for j in [i-k,i-k-1]:
                if j>=0 and check(j,i-1) and 1+f[j]>f[i]:
                    f[i] = 1+f[j]
        return f[-1]

31 ms

目录

2472：不重叠回文子字符串的最大数目（2013 分）

题目

分析

#1

#2

解答