题目描述

给你一个字符串 sequence，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的重复值为 k。单词 word 的最大重复值是单词 word 在 sequence 中最大的重复值。返回单词 word 的最大重复值。

例如：sequence = "ababc"，word = "ab"，输出 2。

解释："abab"（word 重复 2 次）是 "ababc" 的子串；但 "ababab"（重复 3 次）不是 "ababc" 的子串。所以最大重复值为 2。

解题思路

核心思想

要找到 word 重复 k 次后成为 sequence 子串的最大 k 值，我们可以从小到大尝试：

  • 不断将 word 拼接自身，检查拼接后的字符串是否是 sequence 的子串。
  • 只要匹配，就增加计数，继续尝试。
  • 直到匹配失败则停止。

步骤

  1. 初始化计数器 res = 0，保存原始字符串 wordBK = word。
  2. 进入循环：如果 sequence 包含 word：
    • 计数 res++。
    • 将 word 拼接一次自身（word += wordBK），尝试下一个更大的 k 值。
  3. 返回 res。

为什么这种方法可行？

每次拼接后，word 的长度增加 wordBK.length()。当 word 的长度超过 sequence 的长度时，contains() 必然返回 false，循环自动终止。

重复 k 次形成的字符串长度是 k * |word|，因此 k 的最大可能值为 |sequence| / |word|，最多尝试 O(n/m) 次。

示例说明

以 sequence = "ababc"，word = "ab" 为例：

  • word = “ab”：sequence 包含 “ab” ✓，res=1，word = “abab”
  • word = “abab”：sequence 包含 “abab” ✓，res=2，word = “ababab”
  • word = “ababab”：长度 6 > sequence 长度 5，不包含 ✗
  • 返回 2

复杂度分析

  • 时间复杂度：O(n² / m)，最坏情况下需要检查 n/m 次 contains()，每次 O(n)。
  • 空间复杂度：O(n)，拼接的字符串长度最多达到 n。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
package code.J1668;

public class J1668 {
    public int maxRepeating(String sequence, String word) {
        int res = 0;
        String wordBK = word;
        while (sequence.contains(word)) {
            res++;
            word += wordBK;
        }
        return res;
    }
}