[LeetCode][1668. 最大重复子字符串] 不用API，比KMP更易理解简洁优雅的暴力解法

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$ 的更大值。

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

代码如下所示：

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. 😉😃💗