Medium

题目描述

给你一个下标从 0 开始的字符串 word 和一个整数 k。

在每一秒，你必须执行以下操作：

  • 移除 word 的前 k 个字符。
  • 在 word 的末尾添加 k 个字符。

注意，添加的字符不必和你移除的字符相同。但是，你必须在每一秒都执行这两个操作。

返回 word 恢复到初始状态所需的最短时间（大于 0）。

示例 1：

输入：word = "abacaba", k = 3
输出：2
解释：第 1 秒，我们移除 word 的前缀 "aba"，并在末尾添加 "bac"。因此 word 变为 "cababac"。
第 2 秒，我们移除 word 的前缀 "cab"，并在末尾添加 "aba"。因此 word 变为 "abacaba" 并恢复到初始状态。
可以证明，2 秒是 word 恢复到初始状态所需的最短时间（大于 0）。

示例 2：

输入：word = "abacaba", k = 4
输出：1
解释：第 1 秒，我们移除 word 的前缀 "abac"，并在末尾添加 "caba"。因此 word 变为 "abacaba" 并恢复到初始状态。
可以证明，1 秒是 word 恢复到初始状态所需的最短时间（大于 0）。

示例 3：

输入：word = "abcbabcd", k = 2
输出：4
解释：每一秒，我们都移除 word 的前 2 个字符，并在末尾添加相同的字符。
4 秒后，word 变为 "abcbabcd" 并恢复到初始状态。
可以证明，4 秒是 word 恢复到初始状态所需的最短时间（大于 0）。

提示：

  • 1 <= word.length <= 50
  • 1 <= k <= word.length
  • word 仅由小写英文字母组成。

提示：

  • 找到既是后缀又是前缀且长度是 k 的倍数的最长字符串。

解题思路

解题思路

这道题的核心是理解每次操作后字符串的变化规律。每次移除前 k 个字符相当于字符串左移 k 位，而添加的字符可以任意选择，所以关键是找到合适的添加策略使字符串尽快恢复原状。

观察发现，如果我们希望在第 t 次操作后恢复到原始字符串，那么经过 t 次操作后，原字符串的后 n - t*k 个字符（其中 n 是字符串长度）应该与原字符串的前 n - t*k 个字符相同。换句话说，我们需要找到一个长度为 n - t*k 的字符串，它既是原字符串的前缀又是后缀。

具体算法：

  1. 枚举操作次数 t 从 1 开始
  2. 对于每个 t，计算剩余长度 remain = n - t*k
  3. 如果 remain <= 0，说明字符串已经完全被移除，此时可以通过添加原字符串来恢复，返回 t
  4. 否则检查原字符串的前 remain 个字符是否等于后 remain 个字符
  5. 如果相等，说明可以在第 t 次操作后恢复，返回 t

这个方法的时间复杂度是 O(n²/k)，在给定约束下完全可以接受。

另一种优化思路是使用 KMP 算法或 Z 算法预处理前缀后缀匹配信息，但在这个题目的数据规模下，朴素方法已经足够高效。

代码实现

class Solution {
public:
    int minimumTimeToInitialState(string word, int k) {
        int n = word.length();
        
        for (int t = 1; ; t++) {
            int remain = n - t * k;
            if (remain <= 0) {
                return t;
            }
            
            // 检查前remain个字符是否等于后remain个字符
            bool match = true;
            for (int i = 0; i < remain; i++) {
                if (word[i] != word[n - remain + i]) {
                    match = false;
                    break;
                }
            }
            
            if (match) {
                return t;
            }
        }
    }
};

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        
        t = 1
        while True:
            remain = n - t * k
            if remain <= 0:
                return t
            
            # 检查前remain个字符是否等于后remain个字符
            if word[:remain] == word[n-remain:]:
                return t
            
            t += 1

public class Solution {
    public int MinimumTimeToInitialState(string word, int k) {
        int n = word.Length;
        
        for (int t = 1; ; t++) {
            int remain = n - t * k;
            if (remain <= 0) {
                return t;
            }
            
            // 检查前remain个字符是否等于后remain个字符
            bool match = true;
            for (int i = 0; i < remain; i++) {
                if (word[i] != word[n - remain + i]) {
                    match = false;
                    break;
                }
            }
            
            if (match) {
                return t;
            }
        }
    }
}

var minimumTimeToInitialState = function(word, k) {
    const n = word.length;
    
    for (let t = 1; t * k < n; t++) {
        const removed = t * k;
        if (word.substring(removed) === word.substring(0, n - removed)) {
            return t;
        }
    }
    
    return Math.ceil(n / k);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n²/k)
空间复杂度O(1)

说明：

  • 时间复杂度：外层循环最多执行 ⌈n/k⌉ 次，内层字符串比较最多需要 O(n) 时间，总体为 O(n²/k)
  • 空间复杂度：只使用了常数额外空间

相关题目