LeetCode 1668. 最大重复子字符串

2025-10-11 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1668. 最大重复子字符串

题意分析

给定字符串 sequence 和 word，定义「word 的 $k$ 重复串」为把 word 首尾相接写 $k$ 遍得到的字符串。要求最大的 $k$，使得这个 $k$ 重复串是 sequence 的连续子串；若 word 本身都不是 sequence 的子串，返回 $0$。

两个词要抠准：一是「子串」而非「子序列」，必须连续且顺序原样；二是重复必须紧挨着，sequence 中散落的多个 word 不算，比如 "abcab" 里有两个 "ab" 但不相邻，答案只能是 $1$。

约束给得很松：sequence 与 word 长度都不超过 $100$，且都只含小写字母。这个规模等于明说不需要任何高级字符串匹配——KMP、Z 函数、后缀自动机全是过度设计。同时它也给出了答案的天然上界：$k$ 最大只能是 $\lfloor sequence / word \rfloor$，即 $100$ 以内，所以哪怕逐个 $k$ 试过去也不过百次。

边界要盯住两处：word 比 sequence 长时答案必为 $0$，这一支应当由主逻辑自然覆盖而不需要特判；答案为 $0$ 与答案为 $1$ 的区分完全取决于 word 本身是不是子串。

解法：逐次扩展

核心思路

一种思路是枚举 sequence 的每个起点，从那里贪心地一段段匹配 word，看最多能接上几段，取全局最大。这是 $O(n \cdot n)$ 的手写匹配，正确但代码长、边界多。

更简洁的切入点来自一条单调性：如果 word 重复 $k$ 遍是 sequence 的子串，那么重复 $k-1$ 遍必然也是（把 $k$ 重复串的末尾截掉一段 word 即可，它仍是原子串的子串）。也就是说，「$k$ 重复串是否为子串」是关于 $k$ 的单调递减布尔函数，从某个点起由真变假、之后恒假。

有了单调性，只需从 $k = 1$ 开始逐个试，第一次失败时立刻停止，此前成功的次数就是答案——不需要试完所有 $k$，也不会因为跳过某个 $k$ 而漏解。这就是「逐次扩展」的含义。

于是维护两个变量，含义即全程的不变量：sb（或 cur）始终是 word 重复了「已尝试次数」遍的字符串；count 是已经被验证为 sequence 子串的最大重复次数。每一轮先把 sb 追加一份 word（此时它是 count + 1 重复串），再判定：是子串则 count++，进入下一轮；不是则跳出循环返回 count。

循环必然终止：sb 的长度每轮增长 $ word $，一旦超过 $ sequence $ 就绝无可能是子串，判定必假。所以最多迭代 $\lfloor sequence / word \rfloor + 1$ 次。这也顺带把「word 比 sequence 长」的边界消化掉了——第一轮就失败，返回 $0$。

解题步骤

初始化 count = 0 和一个空的可变字符串缓冲区。count 取 $0$ 既是答案下界，也直接给出了「word 都不是子串」这一情形的返回值；缓冲区从空开始，第一轮追加后恰好是 $1$ 重复串。

进入无限循环，每轮开头先追加一份 word。先追加再判定，是因为要检验的永远是「比当前已确认次数多一次」的那个串；反过来先判定再追加会把 $0$ 重复串（空串）也拿去检验，空串恒为子串，导致计数整体偏移。

用子串包含判定检查缓冲区内容是否出现在 sequence 中。这里直接用语言内置的子串查找是合理的：本题的考点是「重复次数的单调性 + 逐次扩展」，而不是手写字符串匹配算法；$n \le 100$ 的规模下，内置实现的朴素 $O(nm)$ 匹配绰绰有余。

命中则 count++ 并继续下一轮，未命中则 break。由单调性保证，一旦失败，更多的重复次数也必然失败，不必再试，提前退出是正确的而非仅仅是优化。

返回 count，即最后一次成功的重复次数。

以 sequence = "ababc"、word = "ab" 走一遍：

初始 count = 0，缓冲区为空。
第 1 轮：追加得 "ab"。"ababc" 中从下标 0 起就是 "ab"，命中，count = 1。
第 2 轮：追加得 "abab"。"ababc" 的前四个字符正是 "abab"，命中，count = 2。
第 3 轮：追加得 "ababab"，长度 $6$ 已超过 sequence 的长度 $5$，必然不是子串，未命中，break。
返回 $2$。

再看一个不相邻的用例 sequence = "abcab"、word = "ab"：第 1 轮 "ab" 命中（下标 0 和下标 3 各有一处），count = 1；第 2 轮 "abab" 在 "abcab" 中不存在——两个 "ab" 被 "c" 隔开，不构成连续重复——未命中，返回 $1$。这个例子正是「重复必须紧挨着」的直接体现，也是最容易被误判成 $2$ 的地方。

最后看返回 $0$ 的情形 sequence = "ababc"、word = "ac"：第 1 轮 "ac" 不是 "ababc" 的子串，直接 break，返回初值 $0$。

代码实现

class Solution {
    public int maxRepeating(String sequence, String word) {
        int count = 0;
        StringBuilder sb = new StringBuilder();

        while (true) {
            sb.append(word);
            if (sequence.contains(sb.toString())) {
                count++;
            } else {
                break;
            }
        }

        return count;
    }
}

func maxRepeating(sequence string, word string) int {
    count := 0
    cur := ""

    for {
        cur += word
        if strings.Contains(sequence, cur) {
            count++
        } else {
            break
        }
    }

    return count
}

复杂度分析

时间复杂度：$O(n^2)$，其中 $n = sequence $、$m = word $。循环轮数至多 $\lfloor n/m \rfloor + 1$；第 $k$ 轮的候选串长 $km$，朴素子串查找的代价是 $O(n \cdot km)$，但一旦 $km > n$ 就立刻失败退出，所以每轮的有效代价都被 $O(n^2)$ 的总量压住。$n \le 100$ 时不过万次字符比较。

空间复杂度：$O(n)$。缓冲区最长会被扩展到略超过 $ sequence $ 的长度（最后一轮失败时），此外只有一个计数器。若改用「枚举起点手写匹配」的写法可以做到 $O(1)$ 额外空间，但代码会长不少。

关键点总结

判定型问题一旦具备单调性（$k$ 可行则 $k-1$ 必可行），就可以从小到大逐次试探并在首次失败时立即停止；规模再大一点还能直接改成对 $k$ 二分。识别单调性是这类题的通用第一步。

「重复 $k$ 次的串是子串」比「找到 $k$ 个不重叠的匹配」严格得多，前者要求这些匹配首尾紧挨。读题时把「连续」「相邻」这类词单独圈出来，它们通常正是唯一的陷阱。

构造式判定往往比匹配式判定好写：与其在 sequence 上找「最多能连续接几个 word」，不如直接把候选串拼出来交给子串查找，逻辑更短、边界更少。

数据范围要用来做减法。$n \le 100$ 时选朴素方案是正确的工程判断，上来就写 KMP 反而暴露了不看约束的习惯。

面试视角：面试官会看你是否第一时间问清「重复必须连续吗」，然后看你能否说出单调性从而证明「首次失败即可停止」。如果他把 $n$ 提到 $10^5$，要能接上：先用 KMP 或 Z 函数把所有 word 的出现位置求出来，再对相邻出现位置做「间隔恰为 $m$ 则链长加一」的动态规划，把复杂度降到 $O(n)$。

易错点总结

先判定再追加 word：第一轮判定的是空串，而空串是任何字符串的子串，count 会先无条件加一，sequence = "ababc"、word = "ac" 会返回 $1$，正确答案是 $0$。

把「重复」理解成「出现多次」：sequence = "abcab"、word = "ab" 会数出两处匹配返回 $2$，但它们不相邻，正确答案是 $1$。

命中后不 break 而是继续试更大的 $k$ 且用 max 更新：逻辑上不会出错，但循环没有终止条件会无限追加 word 直到内存耗尽。

count 初始化为 $1$：sequence = "ababc"、word = "ac" 会返回 $1$，正确答案是 $0$。

每轮重新从 word 构造整个重复串而不是增量追加：结果正确但每轮重建 $O(km)$ 的字符串；真正的错误是重建时写成 word.repeat(count) 而非 count + 1，sequence = "ababc"、word = "ab" 会卡在 $1$ 重复串上死循环。

用 indexOf 判定却写成 >= 0 之外的条件（如 > 0）：sequence = "ababc"、word = "ab" 中 "ab" 出现在下标 $0$，被判成未命中，返回 $0$，正确答案是 $2$。

把子串判定写成 sequence.startsWith(cur)：sequence = "cabab"、word = "ab" 中重复串不在开头，返回 $0$，正确答案是 $2$。

忘记 word 可能比 sequence 长：若在循环外先做 sequence.substring(0, cur.length()) 之类的截取，sequence = "ab"、word = "abc" 会直接抛越界异常，主逻辑本应自然返回 $0$。

把返回值写成缓冲区长度除以 word 长度：最后一轮失败时缓冲区已多追加了一份，sequence = "ababc"、word = "ab" 会返回 $3$，正确答案是 $2$。

用子序列判定代替子串判定：sequence = "axbxaxb"、word = "ab" 按子序列能匹配两遍返回 $2$，而连续子串中 "abab" 并不存在，正确答案是 $0$。

相似题目

题目	难度	考察点
459. 重复的子字符串	简单	反向问「整串能否由某个子串重复构成」，可用 $s+s$ 去头尾的技巧或 KMP 的失配数组
28. 找出字符串中第一个匹配项的下标	简单	本题内部依赖的子串查找本体，考的是朴素匹配与 KMP 的实现
796. 旋转字符串	简单	同为「拼接后判子串」的构造式判定，拼的是 $s+s$ 而非重复 $k$ 次
392. 判断子序列	简单	判定的是子序列而非子串，允许跳字符，双指针即可
187. 重复的DNA序列	中等	找出现次数超过一次的定长子串，靠哈希或滚动哈希，不要求出现位置相邻
1062. 最长重复子串的长度	中等	求最长的出现至少两次的子串，需对长度二分加滚动哈希
1044. 最长重复子串	困难	上一题的大数据版，必须用二分加 Rabin-Karp 才能通过
14. 最长公共前缀	简单	同为逐步扩展候选并在首次失败时停止，扩展的对象是前缀长度