Watch 10 video solutions for Minimum Time to Revert Word to Initial State II, a hard level problem involving String, Rolling Hash, String Matching. This walkthrough by Aryan Mittal has 5,253 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed string word and an integer k.
At every second, you must perform the following operations:
k characters of word.k characters to the end of word.Note that you do not necessarily need to add the same characters that you removed. However, you must perform both operations at every second.
Return the minimum time greater than zero required for word to revert to its initial state.
Example 1:
Input: word = "abacaba", k = 3 Output: 2 Explanation: 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 Explanation: 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 Explanation: 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 <= 1061 <= k <= word.lengthword consists only of lowercase English letters.Problem Overview: You are given a word and an integer k. At every second, the first k characters are removed and any characters can be appended to the end. The task is to determine the minimum time required for the word to become identical to its original state again.
The key observation: after each operation the string effectively shifts left by k positions. The only way the word becomes identical to the original is when the remaining suffix matches the corresponding prefix of the original string.
Approach 1: Full Simulation with String Rotation (O(n^2) time, O(n) space)
This approach directly simulates the process. At each second, remove the first k characters and append arbitrary characters that try to rebuild the original word. After each operation, compare the resulting string with the initial word. Because each comparison takes O(n) and the operation may repeat up to n / k times, the total runtime becomes O(n^2) in the worst case.
The implementation typically uses substring operations or manual rotation logic. While simple to reason about, repeated string copying makes it inefficient for large inputs. This method is mostly useful for validating logic or understanding the transformation process using basic string manipulation.
Approach 2: Optimized Searching for Cycles (Rolling Hash / Prefix Match) (O(n) time, O(n) space)
Instead of simulating every step, observe that after t seconds the first t * k characters of the original word have been removed. The remaining suffix starting at index t * k must match the prefix of the original string for the word to revert correctly.
Iterate over multiples of k and check whether word[i:] matches word[:n-i]. Efficient comparison can be done using string matching techniques or a rolling hash to compare substrings in constant time. The first valid alignment determines the minimum number of seconds required.
Because each candidate alignment is checked once and substring comparisons are constant time with hashing, the total complexity becomes O(n). This avoids repeated string construction and scales well for large inputs.
Recommended for interviews: Interviewers expect the optimized cycle detection idea. The simulation approach shows you understand the transformation, but the rolling-hash or prefix-matching solution demonstrates strong string algorithm knowledge and reduces the runtime from quadratic to linear.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Simulation with String Rotation | O(n^2) | O(n) | Useful for understanding the process or when constraints are very small |
| Optimized Searching for Cycles (Rolling Hash / Prefix Match) | O(n) | O(n) | Best choice for large strings and typical interview expectations |