title
给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：
- 删除 整个字符串
s，或者 - 对于满足
1 <= i <= s.length / 2的任意i，如果s中的 前i个字母和接下来的i个字母 相等 ，删除 前i个字母。
例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s 的前两个字母和接下来的两个字母都等于 "ab" 。
返回删除 s 所需的最大操作数。
示例 1：
输入：s = "abcabcdabc"
输出：2
解释：
- 删除前 3 个字母（"abc"），因为它们和接下来 3 个字母相等。现在，s = "abcdabc"。
- 删除全部字母。
一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。
注意，在第二步操作中无法再次删除 "abc" ，因为 "abc" 的下一次出现并不是位于接下来的 3 个字母。
示例 2：
输入：s = "aaabaab"
输出：4
解释：
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "aabaab"。
- 删除前 3 个字母（"aab"），因为它们和接下来 3 个字母相等。现在，s = "aab"。
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "ab"。
- 删除全部字母。
一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。
示例 3：
输入：s = "aaaaa"
输出：5
解释：在每一步操作中，都可以仅删除 s 的第一个字母。
提示：
1 <= s.length <= 4000s仅由小写英文字母组成
solution
参考 不加特例判断会超时，因此使用hash string更优
class Solution:
def deleteString(self, s: str) -> int:
n = len(s)
if len(set(s)) == 1: return n # 特判全部相同的情况
lcp = [[0] * (n + 1) for _ in range(n + 1)] # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
for i in range(n - 1, -1, -1):
for j in range(n - 1, i, -1):
if s[i] == s[j]:
lcp[i][j] = lcp[i + 1][j + 1] + 1
f = [0] * n
for i in range(n - 1, -1, -1):
for j in range(1, (n - i) // 2 + 1):
if lcp[i][i + j] >= j: # 说明 s[i:i+j] == s[i+j:i+2*j]
f[i] = max(f[i], f[i + j])
f[i] += 1
return f[0]
hash string也会超时
class StringHash:
def __init__(self, s=""):
self.MOD = 998244353
self.BASE = 131
# 计算前缀哈希值
n = len(s)
P = [0] * (n + 1)
P[0] = 1
for i in range(1, n + 1, 1):
P[i] = P[i - 1] * self.BASE % self.MOD
H = [0] * (n + 1)
for i in range(1, n + 1, 1):
H[i] = (H[i - 1] * self.BASE + ord(s[i - 1])) % self.MOD
self.H = H
self.P = P
'''
s的[l,r]区间的hash值，闭区间, l从1开始
'''
def get_hash(self, l=0, r=0):
l, r = l + 1, r + 1
return (self.H[r] - self.H[l - 1] * self.P[r - l + 1] % self.MOD + self.MOD) % self.MOD
class Solution:
def deleteString(self, s: str) -> int:
n = len(s)
dp = [1] * n
hash = StringHash(s)
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if (j - i + 1) % 2 == 0:
mid = (i + j) // 2
if hash.get_hash(i, mid) == hash.get_hash(mid+1, j):
# print(i, j, mid)
dp[i] = max(dp[i], dp[mid+1]+1)
# print(dp[i])
# print(dp)
return dp[0]