Hard

题目描述

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

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

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

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

返回使 word 恢复到其初始状态所需的大于零的最少时间。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= word.length <= 10^6
  • 1 <= k <= word.length
  • word 只包含小写英文字母。

解题思路

这道题的关键是理解操作的本质：每次操作相当于将字符串向左循环移动 k 位。要使字符串恢复到初始状态，我们需要找到最小的正整数 t，使得向左循环移动 t*k 位后字符串不变。

思路分析：

  1. 循环移动的理解：移除前 k 个字符并在末尾添加 k 个字符，等价于将字符串向左循环移动 k 位。

  2. 数学模型：设字符串长度为 n，经过 t 次操作后，字符串向左循环移动了 (t*k) % n 位。要恢复初始状态，需要 (t*k) % n == 0，即 t*k 是 n 的倍数。

  3. 最优解法 - Z函数：我们需要找到最小的 t，使得 word[t*k:] + word[:t*k] 等于原字符串。这等价于找到最长的后缀，它同时也是前缀，且长度是 k 的倍数。

  4. Z函数应用：Z函数可以在 O(n) 时间内计算出每个位置开始的子串与整个字符串的最长公共前缀长度。我们检查所有 k 的倍数位置，找到第一个使得从该位置开始的后缀等于相应前缀的位置。

推荐解法：使用 Z函数，时间复杂度 O(n)，空间复杂度 O(n)。

代码实现

class Solution {
public:
    vector<int> zFunction(string s) {
        int n = s.length();
        vector<int> z(n);
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i <= r) {
                z[i] = min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
    
    int minimumTimeToInitialState(string word, int k) {
        int n = word.length();
        vector<int> z = zFunction(word);
        
        for (int i = k; i < n; i += k) {
            if (z[i] >= n - i) {
                return i / k;
            }
        }
        
        return (n + k - 1) / k;
    }
};

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        def z_function(s):
            n = len(s)
            z = [0] * n
            l, r = 0, 0
            for i in range(1, n):
                if i <= r:
                    z[i] = min(r - i + 1, z[i - l])
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
                if i + z[i] - 1 > r:
                    l, r = i, i + z[i] - 1
            return z
        
        n = len(word)
        z = z_function(word)
        
        for i in range(k, n, k):
            if z[i] >= n - i:
                return i // k
        
        return (n + k - 1) // k

public class Solution {
    private int[] ZFunction(string s) {
        int n = s.Length;
        int[] z = new int[n];
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i <= r) {
                z[i] = Math.Min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
    
    public int MinimumTimeToInitialState(string word, int k) {
        int n = word.Length;
        int[] z = ZFunction(word);
        
        for (int i = k; i < n; i += k) {
            if (z[i] >= n - i) {
                return i / k;
            }
        }
        
        return (n + k - 1) / k;
    }
}

var minimumTimeToInitialState = function(word, k) {
    const n = word.length;
    
    // Build Z-array for the word
    function buildZArray(s) {
        const z = new Array(s.length).fill(0);
        let l = 0, r = 0;
        
        for (let i = 1; i < s.length; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            
            while (i + z[i] < s.length && s[z[i]] === s[i + z[i]]) {
                z[i]++;
            }
            
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        
        return z;
    }
    
    const z = buildZArray(word);
    
    // Check each possible time t
    for (let t = 1; t * k < n; t++) {
        const shift = t * k;
        if (z[shift] >= n - shift) {
            return t;
        }
    }
    
    // If no valid shift found, return ceil(n/k)
    return Math.ceil(n / k);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)Z函数的计算时间复杂度为O(n)，遍历检查的时间复杂度为O(n/k)
空间复杂度O(n)需要额外的数组存储Z函数的结果

相关题目