1668. 最大重复子字符串

LeetCode 原题链接

题目描述

给定字符串 sequence 和 word，返回 word 在 sequence 中的最大连续重复次数。

如果 word 连续重复 k 次后得到的字符串是 sequence 的子字符串，就称 word 是 k 重复字符串：

word 重复 k 次 = word + word + ... + word

例如：

sequence = "ababc"
word = "ab"

其中：

"ab"   是 sequence 的子字符串
"abab" 也是 sequence 的子字符串
"ababab" 不是 sequence 的子字符串

所以最大重复次数是 2。

需要特别注意，题目要求的是连续重复。假如 word 在 sequence 的不同位置分别出现，中间夹着其他字符，就不能累计次数。

题目保证：

  • sequence 和 word 都只包含小写英文字母。
  • 1 <= sequence.length <= 100。
  • 1 <= word.length <= 100，所以 word 不会是空字符串。

为什么可以使用动态规划

假设当前发现一个以位置 i - 1 结尾的 word。要判断它是连续重复中的第几个 word，只需要检查：

紧挨在它前面的字符串，已经连续重复了多少次 word？

这个更小问题的答案已经可以从前面的 DP 状态中得到，因此适合使用动态规划。

DP 状态定义

定义：

dp[i] = 在 sequence 的前 i 个字符中，
        必须以 sequence[i - 1] 结尾的 word 最大连续重复次数

这里的 i 表示前缀长度，不是字符串下标：

dp[i] 对应的最后一个字符下标是 i - 1

例如：

sequence = "ababc"

那么：

dp[2] 处理前 2 个字符 "ab"
dp[4] 处理前 4 个字符 "abab"
dp[5] 处理前 5 个字符 "ababc"

之所以使用“前缀长度”作为 DP 下标，是为了让 dp[0] 自然表示空前缀，并且方便通过 i - word.length 找到当前 word 之前的状态。

状态转移方程

设：

const wordLength = word.length;
const start = i - wordLength;

那么以 i - 1 结尾、长度为 wordLength 的候选片段是：

sequence.slice(start, i);

当前片段不等于 word

如果：

sequence.slice(start, i) !== word

说明不能在位置 i - 1 形成一个完整的 word，因此：

dp[i] = 0;

当前片段等于 word

如果：

sequence.slice(start, i) === word

说明当前位置匹配到了一个完整的 word。

当前 word 前面的结束位置正好是：

start = i - wordLength

而 dp[start] 表示紧挨在当前 word 前面的连续重复次数。因此：

dp[i] = dp[start] + 1;

完整转移为：

if (sequence.slice(start, i) === word) {
  dp[i] = dp[start] + 1;
} else {
  dp[i] = 0;
}

由于 dp 初始化时已经全部填充为 0，代码中可以省略 else。

为什么使用 dp[start] 能保证连续

以：

sequence = "abxxab"
word = "ab"

为例。第二个 "ab" 的起点是下标 4，对应的前缀状态是 dp[4]。

但 sequence 的前 4 个字符是：

"abxx"

它并不以 "ab" 结尾，所以：

dp[4] = 0

第二个 "ab" 匹配成功后只能得到：

dp[6] = dp[4] + 1 = 1

算法不会把开头的 "ab" 和结尾的 "ab" 累计成 2。只有两个 word 首尾紧挨时，前一个状态才会被延续。

初始化与遍历顺序

创建长度为 sequence.length + 1 的数组：

const dp = new Array(sequence.length + 1).fill(0);

其中：

dp[0] = 0

表示空前缀中没有 word。

长度小于 word.length 的前缀不可能容纳一个完整的 word，所以遍历可以直接从：

i = word.length

开始：

for (let i = word.length; i <= sequence.length; i++) {
  // 计算 dp[i]
}

dp[i] 只依赖更早的 dp[i - word.length]，因此必须从左到右计算。

示例推演

以：

sequence = "ababcab"
word = "ab"

为例：

i当前前缀结尾片段dp[i]说明
0""无0空前缀
1"a"长度不足0放不下完整的 "ab"
2"ab""ab"1dp[0] + 1
3"aba""ba"0当前片段不匹配
4"abab""ab"2dp[2] + 1，形成 "abab"
5"ababc""bc"0当前片段不匹配
6"ababca""ca"0当前片段不匹配
7"ababcab""ab"1dp[5] + 1，前面不能连续

最终：

dp = [0, 0, 1, 0, 2, 0, 0, 1]

最大值为 2，对应重复子字符串 "abab"。

代码实现

/**
 * @param {string} sequence
 * @param {string} word
 * @return {number}
 */
var maxRepeating = function (sequence, word) {
  const wordLength = word.length;
  const dp = new Array(sequence.length + 1).fill(0);
  let answer = 0;

  // i 表示当前处理的前缀长度，当前前缀的最后一个字符下标是 i - 1。
  for (let i = wordLength; i <= sequence.length; i++) {
    // 当前候选 word 在 sequence 中的起点。
    const start = i - wordLength;

    // 当前片段匹配 word 时，接在前一个连续重复状态后面。
    if (sequence.slice(start, i) === word) {
      dp[i] = dp[start] + 1;
      answer = Math.max(answer, dp[i]);
    }
  }

  return answer;
};

题目已经保证 word.length >= 1，所以不需要额外处理空字符串。

为什么不能只返回 dp[sequence.length]

dp[i] 表示必须以 sequence[i - 1] 结尾的答案，而最大重复子字符串可能在 sequence 中间结束。

例如：

sequence = "ababx"
word = "ab"

此时：

dp[4] = 2
dp[5] = 0

正确答案是 2，而不是最后一个状态 dp[5]。因此需要在遍历过程中使用 answer 记录所有状态的最大值。

正确性说明

如果当前长度为 word.length 的片段不等于 word，显然不存在以当前位置结尾的有效重复字符串，所以 dp[i] = 0 正确。

如果当前片段等于 word，任何以当前位置结尾的连续重复字符串都由两部分组成：

紧挨在前面的若干个 word + 当前这个 word

前一部分的最大重复次数就是 dp[i - word.length]，所以加上当前匹配的一个 word 后：

dp[i] = dp[i - word.length] + 1;

算法检查了 sequence 中每一个可能的结束位置，并取所有 dp[i] 的最大值，因此不会遗漏答案。

边界情况

  • word.length > sequence.length：循环不会执行，返回 0。
  • sequence === word：对应状态为 dp[word.length] = 1。
  • word 从未出现：所有状态保持为 0。
  • 多次出现但不连续：每段分别从 1 开始，不会错误累计。
  • 存在重叠匹配：算法会检查每个结束位置，但只累计首尾紧挨、间隔正好为 word.length 的匹配。

例如：

sequence = "aaa"
word = "aa"

虽然 "aa" 在下标 0 和下标 1 处各匹配一次，但它们发生重叠，不能组成 "aaaa"，所以答案仍然是 1。

复杂度分析

设：

n = sequence.length
m = word.length

循环最多执行 n 次，每次 slice() 和字符串比较最多处理 m 个字符，因此：

  • 时间复杂度：O(n × m)。
  • 空间复杂度：O(n)，用于保存 dp 数组。

slice() 还可能创建临时字符串。如果希望避免显式截取，也可以写成：

if (sequence.startsWith(word, start)) {
  dp[i] = dp[start] + 1;
}

这不会改变渐进时间复杂度。

替代解法：直接构造

因为题目数据规模很小，也可以不断把 word 追加到候选字符串后面，再用 includes() 判断：

var maxRepeating = function (sequence, word) {
  let repeated = word;
  let answer = 0;

  while (sequence.includes(repeated)) {
    answer++;
    repeated += word;
  }

  return answer;
};

这个写法更短，但会反复创建越来越长的字符串，并且每轮都重新搜索 sequence。DP 写法更直接地利用了相邻匹配之间的关系，也更适合练习状态定义与转移。

常见错误

  • 忘记题目要求连续重复，把不同位置出现的 word 次数直接相加。
  • 把 dp[i] 理解为前 i 个字符中的全局答案，从而错误地直接返回最后一个状态。
  • 当前片段匹配后写成 dp[i - 1] + 1；正确的前一个状态应相隔一个完整的 word.length。
  • 只检查从下标 0 开始的重复，漏掉位于 sequence 中间的答案。
  • 误以为重叠出现的两个 word 可以组成两次连续重复。

一句话总结

当前结尾匹配一个 word 时，
查看它前面紧邻的位置已经连续重复了多少次，再加 1。