Easy

题目描述

对于字符串 sequence，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的重复值为 k。单词的最大重复值是使 word 在 sequence 中具有重复值的最高值 k。如果 word 不是 sequence 的子字符串，那么重复值 k 为 0。

给你字符串 sequence 和 word，返回最大重复值 k。

示例 1：

输入：sequence = "ababc", word = "ab"
输出：2
解释："abab" 是 "ababc" 的子字符串。

示例 2：

输入：sequence = "ababc", word = "ba"
输出：1
解释："ba" 是 "ababc" 的子字符串。"baba" 不是 "ababc" 的子字符串。

示例 3：

输入：sequence = "ababc", word = "ac"
输出：0
解释："ac" 不是 "ababc" 的子字符串。

提示：

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • sequence 和 word 都只包含小写英文字母

解题思路

这道题要求找到 word 在 sequence 中的最大重复次数。

解题思路：

由于题目约束条件相对宽松（字符串长度不超过100），我们可以使用简单的暴力方法。基本思路是从小到大尝试每个可能的 k 值，检查 word 重复 k 次后的字符串是否是 sequence 的子字符串。

具体步骤：

  1. 从 k = 1 开始逐步增加
  2. 构造 word 重复 k 次的字符串
  3. 检查该字符串是否是 sequence 的子字符串
  4. 如果是，继续增加 k；如果不是，返回 k-1

优化考虑：

  • 最大可能的 k 值是 sequence.length / word.length，超过这个值就没必要继续尝试了
  • 可以使用字符串的内置查找函数来检查子字符串

这种方法虽然看起来简单，但对于给定的约束条件是足够高效的。时间复杂度主要取决于字符串匹配的次数和每次匹配的成本。

代码实现

class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int maxK = sequence.length() / word.length();
        
        for (int k = maxK; k >= 1; k--) {
            string repeated = "";
            for (int i = 0; i < k; i++) {
                repeated += word;
            }
            if (sequence.find(repeated) != string::npos) {
                return k;
            }
        }
        
        return 0;
    }
};

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        max_k = len(sequence) // len(word)
        
        for k in range(max_k, 0, -1):
            repeated = word * k
            if repeated in sequence:
                return k
        
        return 0

public class Solution {
    public int MaxRepeating(string sequence, string word) {
        int maxK = sequence.Length / word.Length;
        
        for (int k = maxK; k >= 1; k--) {
            string repeated = "";
            for (int i = 0; i < k; i++) {
                repeated += word;
            }
            if (sequence.Contains(repeated)) {
                return k;
            }
        }
        
        return 0;
    }
}

var maxRepeating = function(sequence, word) {
    const maxK = Math.floor(sequence.length / word.length);
    
    for (let k = maxK; k >= 1; k--) {
        const repeated = word.repeat(k);
        if (sequence.includes(repeated)) {
            return k;
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²/m)n 为 sequence 长度，m 为 word 长度，最多需要检查 n/m 次，每次字符串匹配最坏为 O(n)
空间复杂度O(n)需要存储重复字符串，最长为 sequence 的长度

相关题目