题目描述
给你一个下标从 0 开始的字符串 word
和一个整数 k
。
在每一秒,你必须执行以下操作:
- 移除
word
的前k
个字符。 - 在
word
的末尾添加k
个任意字符。
注意 添加的字符不必和移除的字符相同。但是,必须在每一秒钟都执行 两种 操作。
返回将 word
恢复到其 初始 状态所需的 最短 时间(该时间必须大于零)。
样例
输入:word = "abacaba", k = 3
输出:2
解释:
第 1 秒,移除 word 的前缀 "aba",并在末尾添加 "bac"。
因此,word 变为 "cababac"。
第 2 秒,移除 word 的前缀 "cab",并在末尾添加 "aba"。
因此,word 变为 "abacaba" 并恢复到始状态。
可以证明,2 秒是 word 恢复到其初始状态所需的最短时间。
输入:word = "abacaba", k = 4
输出:1
解释:
第 1 秒,移除 word 的前缀 "abac",并在末尾添加 "caba"。
因此,word 变为 "abacaba" 并恢复到初始状态。
可以证明,1 秒是 word 恢复到其初始状态所需的最短时间。
输入:word = "abcbabcd", k = 2
输出:4
解释:
每一秒,我们都移除 word 的前 2 个字符,并在 word 末尾添加相同的字符。
4 秒后,word 变为 "abcbabcd" 并恢复到初始状态。
可以证明,4 秒是 word 恢复到其初始状态所需的最短时间。
限制
1 <= word.length <= 50
1 <= k <= word.length
word
仅由小写英文字母组成。
算法
(暴力枚举) $O(\frac{n^2}{k})$
- 暴力枚举操作的次数。假设当前操作 $m$ 次,则只需要比对区间 $[0, n - mk)$ 与区间 $[mk, n)$ 是否一致。如果一致,则证明操作 $m$ 次可以回到初始状态。
时间复杂度
- 最多操作 $\lceil \frac{n}{k} \rceil$ 次,每次需要 $O(n)$ 的额外时间判定,故总时间复杂度为 $O(\frac{n^2}{k})$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minimumTimeToInitialState(string word, int k) {
const int n = word.size();
auto check = [&](int m) {
for (int i = 0; i < n - m * k; i++)
if (word[i] != word[i + m * k])
return false;
return true;
};
for (int i = 1; i <= n / k; i++)
if (check(i))
return i;
return (n - 1) / k + 1;
}
};