LogicStack-LeetCode 题解:LeetCode 1668「最大重复子字符串」的序列 DP 与字符串哈希双解法

原创2026-10-08 19:03:181,849 阅读
文章标签:教程文档

LogicStack-LeetCode 题解:LeetCode 1668「最大重复子字符串」的序列 DP 与字符串哈希双解法

本篇技术指南以公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列中 1668. 最大重复子字符串 的题解文档为核心,完整拆解这道入门级「序列 DP」题目:先给出直接截取子串比较的 O(n×m)O(n \times m) 动态规划解法,再引入「字符串哈希」把子串比较降为 O(1)O(1) 数值对比、整体优化到 O(n+m)O(n + m)。读完本文,你将掌握「以结尾位置为状态」的序列 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" 的子字符串

题目约束如下:

  • 1≤sequence.length≤1001 \le sequence.length \le 100
  • 1≤word.length≤1001 \le word.length \le 100
  • sequence 和 word 都只包含小写英文字母

数据范围极小(均不超过 100),因此即便是 O(n×m)O(n \times m) 的朴素做法也能轻松通过;本题的价值更多在于「入门序列 DP 建模」与「用字符串哈希优化找前驱」这两层递进思路,这也是仓库中该题被归类进 Index/序列 DP.md 和 Index/字符串哈希.md 两份索引的原因。

二、解法一:序列 DP(O(n×m)O(n \times m))

2.1 状态定义与转移推导

原文档给出的做法是经典的「以结尾位置为状态」的序列 DP:

定义 f[i]f[i] 为考虑以 ss[i] 结尾时的最大重复值。

之所以强调「以 ss[i] 结尾」,是因为本题要求的是连续重复片段,任何一段合法答案必然对应原串中某个以特定字符结尾、长度恰为 k×mk \times m 的连续子串;以结尾位置收束状态,可以保证转移时片段严格连续。

转移推导(关键一步):由于 pp 的长度 m 已知,每次计算 f[i]f[i] 时,从 ss 中截取以 ss[i] 为结尾、长度为 m 的后缀字符串 sub,并与 pp 做匹配:

  • 若两者相等,说明 sub 贡献了大小为 1 的重复度;
  • 同时,由于 sub 紧贴在前一个合法片段的后面,这个重复度可以累加在 f[i−m]f[i - m] 上(f[i−m]f[i - m] 表示以 ss[i - m] 结尾时的最大重复值,即紧邻 sub 之前的那一段)。

于是得到状态转移方程:

f[i]=f[i−m]+1f[i] = f[i - m] + 1

注意这里的下标设计是自洽的:sub 占用的区间是 ss[i - m + 1 .. i],其前驱位置恰好是 i - m,这正是「好好回想状态定义」后自然得到的转移关系——本题的拓扑序不是由数组下标线性给出的,而是由题目语义中「重复」这一结构决定的,这正是后文要展开的「序列 DP 需要自己找前驱」的特点。

边界与答案统计:

  • 当 i - m < 0 时,无法截取长度为 m 的完整后缀,直接跳过;
  • 每个 f[i]f[i] 计算完毕后,用 ans = Math.max(ans, f[i]) 维护全局最大值;
  • 初始时所有 f[i]=0f[i] = 0,若 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 复杂度分析

  • 时间复杂度:O(n×m)O(n \times m)。外层循环共 nn 个状态,每次转移需要 O(m)O(m) 生成子串并比较;
  • 空间复杂度:O(n)O(n)。仅需一个长度 O(n)O(n) 的动规数组 f(实现中额外开了 n + 10 的冗余空间)。

三、解法二:字符串哈希优化(O(n+m)O(n + m))

3.1 瓶颈定位

解法一的转移瓶颈非常明确:每次都需要花费 O(m)O(m) 的复杂度来生成子串并进行字符串比较。在 n,m≤100n, m \le 100 的数据范围下这不是问题,但一旦把题目推广到更长字符串,O(n×m)O(n \times m) 就不可接受了。

优化思路(原文档的核心手法):把「生成子串 + 逐字符比较」这一 O(m)O(m) 操作,替换为「数值哈希比较」这一 O(1)O(1) 操作。具体来说:

  1. 将 ss 与 pp 拼接得到完整字符串 s = ss + pp;
  2. 以 O(n+m)O(n + m) 复杂度预处理出 s 的哈希数组 h 与次方数组 p;
  3. 从前往后检查 ss,若「某个以 ss[i] 结尾、长度为 m 的后缀子串哈希值」与「pp 字符串的哈希值」相等,说明该位置命中一次 pp,找到前驱状态值 f[i−m]f[i - m] 即可进行转移。

3.2 哈希预处理的底层原理

字符串哈希的核心思想是用一个多项式数值近似表示一个字符串,从而把「子串是否相等」转化为「两个整数是否相等」。预处理公式为(下标从 1 开始):

h[i]=h[i−1]×P+s[i],p[i]=p[i−1]×Ph[i] = h[i - 1] \times P + s[i], \qquad p[i] = p[i - 1] \times P

其中 P 为进制基数。任意区间子串 s[l .. r] 的哈希值可通过前缀哈希在 O(1)O(1) 内得到:

hash(s[l..r])=h[r]−h[l−1]×p[r−l+1]hash(s[l..r]) = h[r] - h[l - 1] \times p[r - l + 1]

在原文档的 Java 实现中,P 取 1313131,哈希值用 long 存储(利用 64 位整型自然溢出取模);Python 实现中 P = 131 并显式对 MOD = 987654321 取模。两者都是「字符串哈希」这一技术在不同语言下的常见落地形态,仓库中 1044. 最长重复子串(字符串哈希 + 二分)与 686. 重复叠加字符串匹配(字符串哈希 / KMP)均使用了完全同构的 h / p 预处理套路,可作为对照阅读。

pp 哈希值的获取技巧:由于我们把 ss 和 pp 拼接成了 s,pp 恰好占据 s 的末尾 m 个字符,因此 pp 的哈希值就是:

phash=h[N]−h[N−m]×p[m]phash = h[N] - h[N - m] \times p[m]

其中 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。

整体效果正如原文档所总结:通过 O(n+m)O(n + m) 复杂度的预处理,将转移过程中「O(m)O(m) 的子串截取与字符串比较」替换成「O(1)O(1) 的数值对比」,整体复杂度从 O(n×m)O(n \times m) 下降到 O(n+m)O(n + m)。

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 复杂度与正确性边界

  • 时间复杂度:O(n+m)O(n + m),预处理 O(n+m)O(n + m),转移过程 O(n)O(n);
  • 空间复杂度:O(n+m)O(n + m),需要存储哈希数组 h、次方数组 p 与动规数组 f。

关于哈希碰撞的说明:字符串哈希本质是以数值近似替代字符串比较,理论上存在不同字符串映射到同一哈希值的概率(碰撞)。在本题 n,m≤100n, m \le 100 的小数据范围下,配合大进制基数(Java 的 long 溢出取模、Python 的大模数取模)碰撞概率极低,是工程与竞赛场景中可接受的近似做法;若追求严格正确,可改用双哈希或直接比较原字符串兜底。仓库 472. 连接词 的题解中对哈希碰撞处理有专门讨论(提及双哈希与「记录哈希值对应了哪些字符串」两种更稳妥的替代方案),可作延伸参考。

四、从本题看「线性 DP」与「序列 DP」的本质区别

原文档在总结部分专门辨析了这两个高频概念,这也是本题作为入门题最值得吸收的「元知识」:

线性 DP:通常强调「状态转移所依赖的前驱状态」由给定数组直接提供,即拓扑序由原数组天然给出——更直白地说,一般形如 f[i][...]f[i][...] 依赖于 f[i−1][...]f[i - 1][...]。因此线性 DP 的复杂度由「状态数量(维度数)」直接决定,转移关系是「送上门」的。

序列 DP:通常需要结合题意自己寻找前驱状态,即需要自行寻找拓扑序关系。本题就是典型例子:转移并非沿下标线性进行,而是由「重复」语义决定——只有当前后缀等于 pp 时,前驱才是 f[i−m]f[i - m],这个「跳跃式」的前驱关系必须从题意中自己提炼出来。

由此可以得出一个重要推论:序列 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. 最长重复子串 字符串哈希 + 二分的典型应用,预处理套路与本题完全一致

六、调试与自测建议

由于题目数据范围极小(n,m≤100n, m \le 100),建议在本地 IDE 或 LeetCode 在线评测中按以下方式验证两份解法的一致性:

  1. 边界用例:word 长度大于 sequence 时(如 sequence = "a", word = "ab"),所有 i - m < 0 成立,答案应为 0;
  2. 完全重叠覆盖:如 sequence = "aaaa", word = "aa",最大重复值应为 2("aaaa" = "aa" + "aa",注意允许片段之间首尾相接、无空余);
  3. 部分命中干扰:如 sequence = "ababc", word = "abc",只有一次命中,答案为 1;
  4. 两解法对拍:随机生成小写字符串,对比序列 DP 版与字符串哈希版的输出是否始终一致,可用于验证哈希实现的边界(尤其是 p[0] = 1 的初始化与 phash 的区间计算)。

综上,本题虽然标记为「简单」,却同时覆盖了「序列 DP 状态设计」「以结尾位置建模」「字符串哈希预处理」「找前驱的复杂度优化」四层核心能力,是仓库「刷穿 LeetCode」系列中性价比极高的一道入门综合题。

登录后查看全文
LogicStack-LeetCode