LeetCode 1668. 最大重复子字符串

约 4 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 京东
标签
字符串 动态规划 字符串匹配

题目描述

✅ 1668. 最大重复子字符串

image-20260928230825011

image-20260928230825012

题意分析

把 word 连续拼接若干次，求拼接结果能作为 sequence 连续子串的最大次数。子串可以从任意位置开始，但多处不相邻的出现不能合并计数；一次也找不到时返回 0。

解法：逐次扩展

核心思路

[!blue]

从一份 word 开始，每次追加一份，检查整个候选串是否出现在 sequence 中。若连续 k 份不存在，更多份也不可能存在：任何更长的重复串都以这 k 份为前缀，它若出现，前面的 k 份也一定出现。因此可行次数从 1 开始连续，第一次失败就能结束。

count 记录已经确认成功的重复次数。每轮追加后，缓冲区保存的是 count+1 份候选；只有查找成功才增加 count，失败时直接返回此前的次数。这样无需扫描候选的每个起点，交给内置子串查找即可。

题目保证 word 非空，候选每轮都会变长。设两串长度为 n、m，最多成功 floor(n/m) 次，再尝试一次必然失败，所以循环一定结束；两串长度都不超过 100，逐次尝试足够。

解题步骤

  • 追加一份 word。
  • 检查整个候选是否为 sequence 的子串。
  • 成功时次数加一，失败时结束。
  • 返回最后成功次数。

代码实现

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;
    }
}

import "strings"

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

    for {
        // 缓冲区是下一次尝试，成功后才增加已确认次数。
        cur += word
        if strings.Contains(sequence, cur) {
            count++
        } else {
            // 当前重复次数不可行，更多次也不可能成为子串。
            break
        }
    }

    return count
}

复杂度分析

  • 时间复杂度：设 q 为实际尝试次数，$q\leq\lfloor n/m\rfloor+1$。第 j 次候选长为 jm，按朴素子串查找的 $O(njm)$ 上界累加，查找总计 $O(nmq^2)$；候选构造和复制另需 $O(mq^2)$，包含在此前上界中。内置查找的实际成本可能更低。
  • 空间复杂度：$O(mq)$，保存候选及转换后的字符串，且 $mq\leq n+m$。

关键点总结

[!green]

  • 重复串必须连续，不能把散落的多次出现相加。
  • 第一次失败即可结束，不会漏掉更大的可行次数。

易错点总结

[!yellow]

  • 只检查 sequence 的开头会漏掉从中间位置开始的重复串，必须判断完整候选是否为子串。
  • 忽略最后失败的一轮，直接用缓冲区长度计算次数，会多算一次。
  • 先检查空缓冲再追加，会把空串也算作一次成功。

相似题目

题目 难度 关联与区别
1566. 重复至少 K 次且长度为 M 的模式 简单 同样要求重复块连续出现，本题模式内容已知并求最大重复次数，原题模式内容由数组窗口决定。
459. 重复的子字符串 简单 原题整个串由一个模式重复构成，本题只需在较大串内部找到连续重复的目标词。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/56094852
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！