#3029

Medium

LeetCode Problem Workspace

Minimum Time to Revert Word to Initial State I

Determine the minimum seconds to revert a string to its original state using repeated prefix shifts of length k efficiently.

string rolling hash string matching hash function

Problem Statement

You are given a 0-indexed string word and an integer k. At every second, remove the first k characters of word and append any k characters to the end. The goal is to find the minimum number of seconds greater than zero required for word to revert to its initial state.

Constraints ensure word length is between 1 and 50, k is between 1 and word.length, and word consists only of lowercase English letters. Efficient handling relies on detecting repeated patterns and rotations using string plus rolling hash techniques.

Examples

Example 1

Input: word = "abacaba", k = 3

Output: 2

At the 1st second, we remove characters "aba" from the prefix of word, and add characters "bac" to the end of word. Thus, word becomes equal to "cababac". At the 2nd second, we remove characters "cab" from the prefix of word, and add "aba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state. It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.

Example 2

Input: word = "abacaba", k = 4

Output: 1

At the 1st second, we remove characters "abac" from the prefix of word, and add characters "caba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state. It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.

Example 3

Input: word = "abcbabcd", k = 2

Output: 4

At every second, we will remove the first 2 characters of word, and add the same characters to the end of word. After 4 seconds, word becomes equal to "abcbabcd" and reverts to its initial state. It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.

Constraints

1 <= word.length <= 50
1 <= k <= word.length
word consists only of lowercase English letters.

Solution Approach

Use Rolling Hash for Prefix-Suffix Matching

Compute hash values for prefixes and suffixes of word to quickly detect matching segments. Focus on suffixes whose length is a multiple of k to find potential cycles without full string comparison.

Determine Minimum Cycle Length

For each candidate suffix length divisible by k, check if repeating the prefix shift operation restores the string. The first length that meets this condition gives the minimum seconds required.

Optimize by Avoiding Full Simulation

Instead of simulating every second, leverage the rolling hash to check repeated rotations efficiently. This reduces time complexity compared to naive simulation, which is essential for larger word lengths.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumeration

Let's assume that if we can restore `word` to its initial state with only one operation, it means that `word[k:]` is a prefix of `word`, i.e., `word[k:] == word[:n-k]`.

1

2

3

4

5

6

7

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

Solution 2: Enumeration + String Hash

Based on Solution 1, we can also use string hashing to determine whether two strings are equal.

1

2

3

4

5

6

7

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

Continue Practicing

#3031 minimum time to revert word to initial state ii #3042 count prefix and suffix pairs i #3045 count prefix and suffix pairs ii