By Long Luo

今天 LeetCode CN 的每日一题是 1668. 最大重复子字符串 ，本文是该题的题解，同时发表在 这里 。

思路

这道题有好几个方法：

1. API：使用 \(String\) \(API\) \(\texttt{contains(CharSequence s)}\) 来判断 \(\textit{sequence}\) 中是否存在拼接的 \(N\) 个 \(\textit{word}\) 字符串；
2. KMP: 使用 KMP 算法判断 \(\textit{sequence}\) 中是否存在拼接的 \(N\) 个 \(\textit{word}\) 字符串；
3. 暴力：判断是否存在拼接的 \(N\) 个 \(\textit{word}\) ，虽然很简单，但代码要写的优雅简洁有难度。

API 方法最简单，但 KMP 算法比较复杂。看了一些题解里的暴力解法，大多数人的暴力解法写的太复杂。我自己写该题暴力解法也写了 \(3\) 个版本，前 \(2\) 个版本也很复杂，逐渐优化为目前的简洁优雅版本。

暴力解法使用 \(2\) 个循环，第 \(1\) 个循环，遍历 \(\textit{sequence}\) 中的每个字符，判断是否和 \(\texttt{word.charAt(0)}\) 相同，相同的话的进入下一步；

使用一个索引 \(j\) ，\(0 \le j \le len - i\) ，而这里 \(\textit{word}\) 字符索引可以使用 \(j \mod wLen\) 来获取，这是暴力解法中最优雅的地方。如果遇到不相同的字符，跳出循环。

最后更新最大重复子字符串，就是 \(\textit{ans}\) 和 \(j / wLen\) 的更大值。

中间其实还可以剪枝，但由于数据量比较小，就不加了。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int maxRepeating(String sequence, String word) {
        int sLen = sequence.length();
        int wLen = word.length();

        int ans = 0;

        for (int i = 0; i < sLen; i++) {
            if (sequence.charAt(i) != word.charAt(0)) {
                continue;
            }
            
            int j = 0;
            while (i + j < sLen && sequence.charAt(i + j) == word.charAt(j % wLen)) {
                j++;
            }

            ans = Math.max(ans, j / wLen);
        }

        return ans;
    }
}

复杂度分析

• 时间复杂度：\(O(n^2)\) ，其中 \(n\) 是字符串 \(\textit{sequence}\) 长度，存在 \(2\) 个循环，所以总时间复杂度为 \(O(n^2)\) 。
• 空间复杂度：\(O(1)\) 。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗