LeetCode 1062. 最长重复子串的长度
题目描述
题意分析
在同一个字符串中，寻找至少出现两次的最长连续片段，返回它的长度；如果不存在重复子串，返回零。两次出现的起点必须不同，但允许它们的覆盖范围重叠。
“子串”要求字符连续，不能跳过不匹配字符。只需返回长度，不需要输出子串或所有位置；同一片段出现超过两次也合法。不能把同一个位置的片段与自身比较，否则任何字符串都会得到整串长度。
解法：公共后缀动态规划
核心思路
[!blue]
把字符串与自身比较，但只比较两个不同的结束位置。设
dp[i][j]表示分别以s[i - 1]和s[j - 1]结尾的最长相同连续片段长度，下标i、j表示已取到的前缀长度。如果末尾字符相同，就能把之前两个位置结尾的公共片段同时延长一位，因此
dp[i][j] = dp[i - 1][j - 1] + 1。如果末尾不同，以这两个位置结尾的公共子串就无法存在，状态必须为零，不能取相邻状态最大值来跳过字符；那会变成子序列问题。只计算
i < j的上三角状态即可。任意两个不同出现位置总能把较早者放在前面，这不会漏掉重复；同时排除了i == j的自身匹配。转移始终沿左上对角线进行，两次出现的间隔不变，因此即使重复片段重叠，也会自然被计入，不应额外限制长度小于位置间隔。每个状态只依赖上一行的左上角，可以压缩为一个数组。处理当前
i时，让j从字符串末尾倒序到i + 1，读取的dp[j - 1]尚未在本轮更新，仍代表上一行。初始全零对应空前缀。每次更新后记录最大值，因为最长重复子串可能结束在任意两个位置，而不是一定结束在串尾。
解题步骤
- 创建长度为
n + 1的全零数组dp，答案best初始为零。- 用
i = 1..n-1枚举较早的结束位置。- 用
j = n..i+1倒序枚举较晚的结束位置，比较s[i - 1]与s[j - 1]。- 相等时令
dp[j] = dp[j - 1] + 1，不等时令dp[j] = 0。- 用当前状态更新
best，全部结束后返回它。
代码实现
class Solution {
public int longestRepeatingSubstring(String s) {
int n = s.length();
int[] dp = new int[n + 1];
int best = 0;
for (int i = 1; i < n; i++) {
// 只比较不同结束位置，倒序保证左上来源仍是上一行。
for (int j = n; j > i; j--) {
if (s.charAt(i - 1) == s.charAt(j - 1)) {
// 相等时延长公共后缀，重叠的两次出现仍可计入。
dp[j] = dp[j - 1] + 1;
} else {
// 不等立即中断连续匹配，不能沿用旧长度。
dp[j] = 0;
}
best = Math.max(best, dp[j]);
}
}
return best;
}
}
func longestRepeatingSubstring(s string) int {
n := len(s)
dp := make([]int, n+1)
best := 0
for i := 1; i < n; i++ {
// 只比较不同结束位置，倒序保证左上来源仍是上一行。
for j := n; j > i; j-- {
if s[i-1] == s[j-1] {
// 相等时延长公共后缀，重叠的两次出现仍可计入。
dp[j] = dp[j-1] + 1
} else {
// 不等立即中断连续匹配，不能沿用旧长度。
dp[j] = 0
}
if dp[j] > best {
best = dp[j]
}
}
}
return best
}
复杂度分析
- 时间复杂度：
O(n²)。只枚举不同结束位置组成的上三角区域，共n(n - 1)/2个状态，每次转移为常数时间。- 空间复杂度：
O(n)。通过倒序更新仅保留一行公共后缀长度。
关键点总结
[!green]
- 状态限定两个结束位置，才能用末尾字符是否相等直接延长或归零。
- 不同位置排除自身匹配，允许重叠则保留全部合法重复片段。
- 倒序读取旧左上状态，全局最大值覆盖所有可能的结束位置。
易错点总结
[!yellow]
- 把
i == j也纳入答案：同一个片段与自身匹配会制造整串长度的假答案。- 不匹配时保留旧值或取相邻最大值：会跨越断点，错误地允许不连续匹配。
- 从小到大更新
j：左侧状态已经属于本轮，不能再当作上一行的左上来源。- 禁止重复区间相交：题目允许重叠，只需要两次出现的位置不同。
- 只返回最后一个状态：最长片段不一定在最后位置结束，必须在整个计算过程中取最大值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 718. 最长重复子数组 | 中等 | 同样比较连续片段，原题在两个数组之间求公共长度，本题在同一串的不同位置之间。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！