What is the main trick to solving Minimum Time to Revert Word to Initial State I?

The main trick is using rolling hash to detect suffixes that match prefixes with length divisible by k, allowing quick cycle detection.

Can this problem be solved without rolling hash?

Yes, but naive simulation is less efficient; rolling hash speeds up comparisons and avoids repeated string operations.

Why must the suffix length be a multiple of k?

Only suffixes whose length is divisible by k align correctly with the repeated prefix removal and append operations to form a cycle.

What are common mistakes in this problem?

Ignoring cycles shorter than full string length, not considering multiples of k, and simulating each second unnecessarily.

How does the string plus rolling hash pattern apply here?

It helps efficiently compare rotated string segments, detect repeating cycles, and compute minimum seconds without full simulation.

#3029

Medium

auto_awesomestring·结合·rolling·哈希

LeetCode 题解工作台

将单词恢复初始状态所需的最短时间 I

给你一个下标从 0 开始的字符串 word 和一个整数 k 。在每一秒，你必须执行以下操作：移除 word 的前 k 个字符。在 word 的末尾添加 k 个任意字符。注意添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行两种操作。返回将 word 恢复到其初始状态所需的…

字符串滚动哈希字符串匹配哈希函数

题目描述

给你一个下标从 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 个字符，并在 word 末尾添加相同的字符。
4 秒后，word 变为 "abcbabcd" 并恢复到初始状态。
可以证明，4 秒是 word 恢复到其初始状态所需的最短时间。

提示：

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

lightbulb

解题思路

方法一：枚举

我们不妨假设，如果只操作一次，就能使得 word 恢复到初始状态，那么意味着 word[k:] 是 word 的前缀，即 word[k:] == word[:n-k]。

如果有多次操作，不妨设 $i$ 为操作次数，那么意味着 word[k*i:] 是 word 的前缀，即 word[k*i:] == word[:n-k*i]。

因此，我们可以枚举操作次数，判断 word[k*i:] 是否是 word 的前缀，如果是，则返回 $i$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为 word 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        for i in range(k, n, k):
            if word[i:] == word[:-i]:
                return i // k
        return (n + k - 1) // k

speed

复杂度分析

指标	值
时间	complexity depends on rolling hash computation and checking all valid suffix lengths, roughly O(n^2/k). Space complexity is O(n) for storing hash values of prefixes and suffixes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on string transformations that can be represented as rotations.
question_mark
Look for repeated patterns that align with multiples of k.
question_mark
Consider hashing to compare string segments efficiently.

warning

常见陷阱

外企场景

error
Simulating each second instead of using hash leads to unnecessary computations.
error
Ignoring that only suffix lengths multiple of k are valid for rotations.
error
Overlooking small cycles that restore the original string quickly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing k dynamically at each step requiring adjusted suffix-prefix checks.
arrow_right_alt
Allowing insertions of different characters instead of rotating existing ones.
arrow_right_alt
Larger strings where naive simulation becomes impractical, emphasizing hashing.

help

常见问题

外企场景

继续练习

#3031 将单词恢复初始状态所需的最短时间 II #3042 统计前后缀下标对 I #3045 统计前后缀下标对 II