LeetCode - 1668. 最大重复子字符串

题目

1668. 最大重复子字符串 - 力扣（LeetCode）

解题思路

滑动窗口法的核心是从序列的每个可能的起始位置开始，尝试找出最多连续重复的word子串。

详细步骤

遍历可能的起始位置：

• 从序列的开始位置到 n - m 位置（其中n是序列长度，m是word长度），这样可以确保至少有一个完整的word可以被检查

对每个起始位置进行检查：

• 从当前位置i开始

• 初始化计数器count = 0

• 设置一个指针j从i开始

连续匹配：

• 检查从j位置开始的m个字符是否与word相同

• 如果相同，增加count，并将j向后移动m个位置（即word的长度）

• 继续检查下一个可能的word位置

• 直到不匹配或到达序列末尾

更新最大值：

• 对于每个起始位置，记录找到的最大连续重复次数

读者可能出现的错误写法

class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int m = sequence.size();
        int n = word.size();
        int maxCount = 0;

        for(int i = 0; i < m-n; i++)
        {
            int count = 0;
            int j = i;
            while(j+n < m && sequence.substr(j,n) == word)
            {
                count++;
                j = j+n;
            }
            maxCount = max(maxCount,count);
        }
        return maxCount;
    }
};

for循环条件错误：

   for(int i = 0; i < m-n; i++)

这里的条件是 i < m-n，其中 m 是 sequence 的长度，n 是 word 的长度。

当 word 的长度小于或等于 sequence 的长度时（正常情况），m-n 会是负数或零，导致循环一次都不执行。

正确的条件应该是 i <= m-n（如果 m≥n）或者更准确地说是 i <= m-n（当 m≥n 时）。

while循环条件错误：

   while(j+n < m && sequence.substr(j,n) == word)

这个条件也有问题。j+n < m 检查是否超出序列边界，但实际上应该是 j+n <= m。

对于测试用例 sequence = "a" 和 word = "a"：

• m = 1 (sequence的长度)

• n = 1 (word的长度)

• 循环条件 i < m-n 变成 i < 0，循环不会执行

• 所以返回初始值 maxCount = 0

但正确答案应该是 1，因为 "a" 在 "a" 中出现了 1 次。

正确的写法

int maxRepeating(string sequence, string word) {
    int m = sequence.size();
    int n = word.size();
    int maxCount = 0;
    
    // 只有当word长度小于等于sequence长度时才能进行匹配
    if (n > m) return 0;
    
    // 遍历所有可能的起始位置
    for(int i = 0; i <= m-n; i++) {
        int count = 0;
        int j = i;
        
        // 从位置j开始，尝试匹配连续的word
        while(j+n <= m && sequence.substr(j,n) == word) {
            count++;
            j += n;
        }
        
        maxCount = max(maxCount, count);
    }
    
    return maxCount;
}