LogicStack-LeetCode 题解:LeetCode 1668「最大重复子字符串」的序列 DP 与字符串哈希双解法
LogicStack-LeetCode 题解:LeetCode 1668「最大重复子字符串」的序列 DP 与字符串哈希双解法
本篇技术指南以公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列中 1668. 最大重复子字符串 的题解文档为核心,完整拆解这道入门级「序列 DP」题目:先给出直接截取子串比较的 动态规划解法,再引入「字符串哈希」把子串比较降为 数值对比、整体优化到 。读完本文,你将掌握「以结尾位置为状态」的序列 DP 建模方法、字符串哈希预处理的完整套路,并理清「线性 DP」与「序列 DP」的本质差异,这些能力可直接复用到仓库中 Index/序列 DP.md 与 Index/字符串哈希.md 收录的十余道同类题目。
一、题目理解:重复值到底在求什么
1.1 题意与术语约定
题目给定两个字符串 sequence 与 word:
- 若
word连续重复k次形成的字符串是sequence的一个子字符串,则word的重复值为k; word的最大重复值是word在sequence中能取到的最大k;- 若
word根本不是sequence的子串,重复值为0。
注意关键限定词「连续重复」:即要求 sequence 中存在一段形如 word + word + ... + word 的连续片段,中间不能插入其他字符,这与「子序列」问题有本质区别。
为方便推导,原文档做了如下记号约定:将 sequence 记为 ss,将 word 记为 pp,两者长度分别记为 n 和 m;同时把「字符串」以及「动规数组」的下标统一调整为从 1 开始。
1.2 三个示例与边界约束
| 输入 | 输出 | 解释 |
|---|---|---|
sequence = "ababc",word = "ab" |
2 |
"abab" 是 "ababc" 的子字符串 |
sequence = "ababc",word = "ba" |
1 |
"ba" 是子串,但 "baba" 不是 |
sequence = "ababc",word = "ac" |
0 |
"ac" 不是 "ababc" 的子字符串 |
题目约束如下:
sequence和word都只包含小写英文字母
数据范围极小(均不超过 100),因此即便是 的朴素做法也能轻松通过;本题的价值更多在于「入门序列 DP 建模」与「用字符串哈希优化找前驱」这两层递进思路,这也是仓库中该题被归类进 Index/序列 DP.md 和 Index/字符串哈希.md 两份索引的原因。
二、解法一:序列 DP()
2.1 状态定义与转移推导
原文档给出的做法是经典的「以结尾位置为状态」的序列 DP:
定义 为考虑以
ss[i]结尾时的最大重复值。
之所以强调「以 ss[i] 结尾」,是因为本题要求的是连续重复片段,任何一段合法答案必然对应原串中某个以特定字符结尾、长度恰为 的连续子串;以结尾位置收束状态,可以保证转移时片段严格连续。
转移推导(关键一步):由于 pp 的长度 m 已知,每次计算 时,从 ss 中截取以 ss[i] 为结尾、长度为 m 的后缀字符串 sub,并与 pp 做匹配:
- 若两者相等,说明
sub贡献了大小为1的重复度; - 同时,由于
sub紧贴在前一个合法片段的后面,这个重复度可以累加在 上( 表示以ss[i - m]结尾时的最大重复值,即紧邻sub之前的那一段)。
于是得到状态转移方程:
注意这里的下标设计是自洽的:sub 占用的区间是 ss[i - m + 1 .. i],其前驱位置恰好是 i - m,这正是「好好回想状态定义」后自然得到的转移关系——本题的拓扑序不是由数组下标线性给出的,而是由题目语义中「重复」这一结构决定的,这正是后文要展开的「序列 DP 需要自己找前驱」的特点。
边界与答案统计:
- 当
i - m < 0时,无法截取长度为m的完整后缀,直接跳过; - 每个 计算完毕后,用
ans = Math.max(ans, f[i])维护全局最大值; - 初始时所有 ,若
pp从未作为子串出现过,答案自然保持为0,与题意「不是子串则重复值为 0」吻合。
2.2 完整代码
原文档给出了 Java、TypeScript、Python 三个版本的实现,内容如下:
Java 代码:
class Solution {
public int maxRepeating(String ss, String pp) {
int n = ss.length(), m = pp.length(), ans = 0;
int[] f = new int[n + 10];
for (int i = 1; i <= n; i++) {
if (i - m < 0) continue;
if (ss.substring(i - m, i).equals(pp)) f[i] = f[i - m] + 1;
ans = Math.max(ans, f[i]);
}
return ans;
}
}
TypeScript 代码:
function maxRepeating(ss: string, pp: string): number {
let n = ss.length, m = pp.length, ans = 0
const f = new Array<number>(n + 10).fill(0)
for (let i = 1; i <= n; i++) {
if (i - m < 0) continue
if (ss.substr(i - m, i) == pp) f[i] = f[i - m] + 1
ans = Math.max(ans, f[i])
}
return ans
}
Python 代码:
class Solution:
def maxRepeating(self, ss: str, pp: str) -> int:
n, m, ans = len(ss), len(pp), 0
f = [0] * (n + 10)
for i in range(1, n + 1):
if i - m < 0:
continue
if ss[i - m:i] == pp:
f[i] = f[i - m] + 1
ans = max(ans, f[i])
return ans
一处实用的语言细节:TypeScript 版中 ss.substr(i - m, i) 的第二参数是「截取长度」而非结束下标(与 Java 的 substring(begin, end)、Python 的切片 ss[i - m : i] 语义不同),严格对应题意应使用 ss.slice(i - m, i) 或 ss.substring(i - m, i),此处保留原文档写法便于对照三份实现,实际提交时建议按目标语言的切片语义核对一遍。
2.3 复杂度分析
- 时间复杂度:。外层循环共 个状态,每次转移需要 生成子串并比较;
- 空间复杂度:。仅需一个长度 的动规数组
f(实现中额外开了n + 10的冗余空间)。
三、解法二:字符串哈希优化()
3.1 瓶颈定位
解法一的转移瓶颈非常明确:每次都需要花费 的复杂度来生成子串并进行字符串比较。在 的数据范围下这不是问题,但一旦把题目推广到更长字符串, 就不可接受了。
优化思路(原文档的核心手法):把「生成子串 + 逐字符比较」这一 操作,替换为「数值哈希比较」这一 操作。具体来说:
- 将
ss与pp拼接得到完整字符串s = ss + pp; - 以 复杂度预处理出
s的哈希数组h与次方数组p; - 从前往后检查
ss,若「某个以ss[i]结尾、长度为m的后缀子串哈希值」与「pp字符串的哈希值」相等,说明该位置命中一次pp,找到前驱状态值 即可进行转移。
3.2 哈希预处理的底层原理
字符串哈希的核心思想是用一个多项式数值近似表示一个字符串,从而把「子串是否相等」转化为「两个整数是否相等」。预处理公式为(下标从 1 开始):
其中 P 为进制基数。任意区间子串 s[l .. r] 的哈希值可通过前缀哈希在 内得到:
在原文档的 Java 实现中,P 取 1313131,哈希值用 long 存储(利用 64 位整型自然溢出取模);Python 实现中 P = 131 并显式对 MOD = 987654321 取模。两者都是「字符串哈希」这一技术在不同语言下的常见落地形态,仓库中 1044. 最长重复子串(字符串哈希 + 二分)与 686. 重复叠加字符串匹配(字符串哈希 / KMP)均使用了完全同构的 h / p 预处理套路,可作为对照阅读。
pp 哈希值的获取技巧:由于我们把 ss 和 pp 拼接成了 s,pp 恰好占据 s 的末尾 m 个字符,因此 pp 的哈希值就是:
其中 N 为拼接后的总长度。这样我们不需要额外为 pp 单独算一遍哈希,直接复用 s 的哈希数组即可。
3.3 转移过程
在动规主循环中,对于每个 i:
- 若
i - m < 0,跳过; - 否则计算以
ss[i]结尾、长度为m的子串哈希:cur = h[i] - h[i - m] * p[m]; - 若
cur == phash,说明这一段就是pp,执行f[i] = f[i - m] + 1; - 维护全局最大值
ans。
整体效果正如原文档所总结:通过 复杂度的预处理,将转移过程中「 的子串截取与字符串比较」替换成「 的数值对比」,整体复杂度从 下降到 。
3.4 完整代码
Java 代码:
class Solution {
public int maxRepeating(String ss, String pp) {
int n = ss.length(), m = pp.length(), ans = 0;
int[] f = new int[n + 10];
String s = ss + pp;
int P = 1313131, N = s.length();
long[] h = new long[N + 10], p = new long[N + 10];
p[0] = 1;
for (int i = 1; i <= N; i++) {
h[i] = h[i - 1] * P + s.charAt(i - 1);
p[i] = p[i - 1] * P;
}
long phash = h[N] - h[N - m] * p[m];
for (int i = 1; i <= n; i++) {
if (i - m < 0) continue;
long cur = h[i] - h[i - m] * p[m];
if (cur == phash) f[i] = f[i - m] + 1;
ans = Math.max(ans, f[i]);
}
return ans;
}
}
Python 代码:
class Solution:
def maxRepeating(self, ss: str, pp: str) -> int:
n, m, ans = len(ss), len(pp), 0
f = [0] * (n + 10)
s = ss + pp
P, N, MOD = 131, len(s), 987654321
h, p = [0] * (N + 10), [0] * (N + 10)
p[0] = 1
for i in range(1, N + 1):
h[i] = (h[i - 1] * P + ord(s[i - 1])) % MOD
p[i] = (p[i - 1] * P) % MOD
phash = (h[N] - h[N - m] * p[m]) % MOD
for i in range(1, n + 1):
if i - m < 0:
continue
cur = (h[i] - h[i - m] * p[m]) % MOD
if cur == phash:
f[i] = f[i - m] + 1
ans = max(ans, f[i])
return ans
3.5 复杂度与正确性边界
- 时间复杂度:,预处理 ,转移过程 ;
- 空间复杂度:,需要存储哈希数组
h、次方数组p与动规数组f。
关于哈希碰撞的说明:字符串哈希本质是以数值近似替代字符串比较,理论上存在不同字符串映射到同一哈希值的概率(碰撞)。在本题 的小数据范围下,配合大进制基数(Java 的 long 溢出取模、Python 的大模数取模)碰撞概率极低,是工程与竞赛场景中可接受的近似做法;若追求严格正确,可改用双哈希或直接比较原字符串兜底。仓库 472. 连接词 的题解中对哈希碰撞处理有专门讨论(提及双哈希与「记录哈希值对应了哪些字符串」两种更稳妥的替代方案),可作延伸参考。
四、从本题看「线性 DP」与「序列 DP」的本质区别
原文档在总结部分专门辨析了这两个高频概念,这也是本题作为入门题最值得吸收的「元知识」:
线性 DP:通常强调「状态转移所依赖的前驱状态」由给定数组直接提供,即拓扑序由原数组天然给出——更直白地说,一般形如 依赖于 。因此线性 DP 的复杂度由「状态数量(维度数)」直接决定,转移关系是「送上门」的。
序列 DP:通常需要结合题意自己寻找前驱状态,即需要自行寻找拓扑序关系。本题就是典型例子:转移并非沿下标线性进行,而是由「重复」语义决定——只有当前后缀等于 pp 时,前驱才是 ,这个「跳跃式」的前驱关系必须从题意中自己提炼出来。
由此可以得出一个重要推论:序列 DP 的复杂度由「状态数 + 找前驱」的复杂度共同决定。这也直接导致了序列 DP 玩法丰富,常常可以结合其他知识点出题来优化「找前驱」这一操作——通常手段是利用某些性质(如本题的哈希化整为零),或是利用数据结构(如 1218. 最长定差子序列 用哈希表记录值域状态快速找前驱、Index/序列 DP.md 中多题结合二分/哈希/排序优化转移)。
五、仓库延伸:同类题目与索引体系
本题收录于本仓库 LeetCode/1661-1670/ 目录,并同时出现在三份专题索引中,可作为系统刷题路线的入口:
- Index/序列 DP.md:收录 139、334、354、472、583、1218、1668、1691、1713、1751 等二十余道序列 DP 题目,每行均带题解链接与推荐指数;
- Index/字符串哈希.md:收录 187、472、686、1044、1668、面试题 01.09 等字符串哈希题目;
- Index/线性 DP.md:收录 10、44、53、91、198、403、1220 等线性 DP 题目,可与上文的「线性 vs 序列」辨析对照阅读。
与本题高度相关的四道姊妹题,建议按序精读:
| 题目 | 关联点 |
|---|---|
| 139. 单词拆分 | 同为字符串上的序列 DP,但找前驱依赖字典,是本题的「放宽版」 |
| 472. 连接词 | 序列 DP + 字符串哈希的进阶组合,还涉及哈希碰撞处理 |
| 686. 重复叠加字符串匹配 | 方向相反:已知重复次数上限求匹配,字符串哈希 / KMP 双解 |
| 1044. 最长重复子串 | 字符串哈希 + 二分的典型应用,预处理套路与本题完全一致 |
六、调试与自测建议
由于题目数据范围极小(),建议在本地 IDE 或 LeetCode 在线评测中按以下方式验证两份解法的一致性:
- 边界用例:
word长度大于sequence时(如sequence = "a",word = "ab"),所有i - m < 0成立,答案应为0; - 完全重叠覆盖:如
sequence = "aaaa",word = "aa",最大重复值应为2("aaaa" = "aa" + "aa",注意允许片段之间首尾相接、无空余); - 部分命中干扰:如
sequence = "ababc",word = "abc",只有一次命中,答案为1; - 两解法对拍:随机生成小写字符串,对比序列 DP 版与字符串哈希版的输出是否始终一致,可用于验证哈希实现的边界(尤其是
p[0] = 1的初始化与phash的区间计算)。
综上,本题虽然标记为「简单」,却同时覆盖了「序列 DP 状态设计」「以结尾位置建模」「字符串哈希预处理」「找前驱的复杂度优化」四层核心能力,是仓库「刷穿 LeetCode」系列中性价比极高的一道入门综合题。