1668. 最大重复子字符串

🟢   🔖  字符串 动态规划 字符串匹配  🔗 力扣 LeetCode

题目

For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word's maximumk-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word's maximum k-repeating value is 0.

Given strings sequence and word, return themaximumk-repeating value of word in sequence.

Example 1:

Input: sequence = "ababc", word = "ab"

Output: 2

Explanation: "abab" is a substring in "abab c".

Example 2:

Input: sequence = "ababc", word = "ba"

Output: 1

Explanation: "ba" is a substring in "a ba bc". "baba" is not a substring in "ababc".

Example 3:

Input: sequence = "ababc", word = "ac"

Output: 0

Explanation: "ac" is not a substring in "ababc".

Constraints:

• 1 <= sequence.length <= 100
• 1 <= word.length <= 100
• sequence and word contains only lowercase English letters.

题目大意

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

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

示例 1：

输入： sequence = "ababc", word = "ab"

输出： 2

解释： "abab" 是 "abab c" 的子字符串。

示例 2：

输入： sequence = "ababc", word = "ba"

输出： 1

解释： "ba" 是 "aba bc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。

示例 3：

输入： sequence = "ababc", word = "ac"

输出： 0

解释： "ac" 不是 "ababc" 的子字符串。

提示：

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

解题思路

通过逐步构造 word 的重复形式，并检查它是否是 sequence 的子串，可以得到最大重复次数。

1. 初始化 res = 0，表示当前最大的重复次数。

2. 使用 String.prototype.includes 方法来判断 sequence 是否包含 word 的 (res + 1) 次重复。

   • 如果包含，则增加 res，继续检查更高的重复次数。

3. 当 sequence 不再包含 word 的 (res + 1) 次重复时，停止循环，返回 res。

复杂度分析

• 时间复杂度：O(k * n)，其中 k 是最大重复次数，n 是 sequence 的长度。

  • 每次生成的重复字符串并检查是否为子串的时间复杂度为O(n)；
  • 一共检查 k 次。

• 空间复杂度：O(k * m)，其中 k 是最大重复次数，m 是 word 的长度。每次生成的重复字符串需要占用额外空间，其长度为 (res + 1) * m。

代码

/**
 * @param {string} sequence
 * @param {string} word
 * @return {number}
 */
var maxRepeating = function (sequence, word) {
	let res = 0;
	while (sequence.includes(word.repeat(res + 1))) {
		res++;
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
1566	重复至少 K 次且长度为 M 的模式	[✓]	数组 枚举	🟢	🀄️ 🔗
3137	K 周期字符串需要的最少操作次数		哈希表 字符串 计数	🟠	🀄️ 🔗