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.
The idea is to simulate the operations step by step until the string reverts back to its initial state. By removing the first k characters and appending them at the end, we effectively rotate the string. We repeat this operation until the string matches its initial configuration.
This C program simulates the operations step by step. Each time it removes the first k characters and appends them to the end, forming a rotated version of the string. The process continues until the string reverts to its original state, and the time is returned.
Time Complexity: O(n^2) due to repeated rotations of strings of length n.
Space Complexity: O(n) for the temporary storage of strings.
Instead of simulating every operation, we can determine when the string has completed a cycle by using an efficient cycling strategy. Recognize that the rotation step can be skipped through mathematical reasoning about the Least Common Multiple (LCM) of rotations and the string length.
This C solution calculates the greatest common divisor (GCD) of the word length and k to find the minimal rotations needed to revert the word to its original configuration.
Time Complexity: O(log(min(n, k)))
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Full Simulation with String Rotation | Time Complexity: |
| Optimized Searching for Cycles | Time Complexity: |
| Default Approach | — |
| 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 |
3031. Minimum Time to Revert Word to Initial State II | KMP | Weekly Contest 383 | String Matching • Aryan Mittal • 5,253 views views
Watch 9 more video solutions →Practice Minimum Time to Revert Word to Initial State II with our built-in code editor and test cases.
Practice on FleetCode