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 <= 50 1 <= k <= word.lengthword consists only of lowercase English letters.In this approach, we simulate the operations one step at a time. We perform the operations as described — remove the first k characters and append any k characters at the end — and track the state of the string at each step. We stop when the string matches the original string. The approach utilizes a set to track previously seen states for efficiency.
This C program initializes a current state of the word, performs the operation to shift the characters, and checks after each operation if the state reverts to the initial state. It counts the number of operations required and returns this count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n2) where n is the length of the word, owing to repeated string operations. Space Complexity: O(n) for storing intermediate string states.
In this approach, instead of simulating each step, we analyze the shifts to determine effectively when the string will return to its initial state by determining cycle lengths. This involves understanding how many shifts (or character position changes) it takes to revert to the start configuration based on modular arithmetic and greatest common divisors (GCD).
This C code calculates the least number of shifts needed for the word to revert to its starting state using the concept of cycles and their GCD. The formula derives from observations on modular rotations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log(n+k)) due to the GCD calculation. Space Complexity: O(1) since it only utilizes a constant amount of additional space.
In this approach, we simulate each transformation step-by-step. In every second, we remove the first k characters and append them to the end. We repeat this until the string matches its initial state. This solution exploits the maximum constraints to provide a simple, albeit not the most performant, method to solve the problem.
The function initializes the original word and sets a counter. It then enters a loop where it slices the first k characters and appends them to the end. This process continues until the word returns to its original state, and the counter value is returned.
JavaScript
Time Complexity: O(n), where n is the length of the word.
Space Complexity: O(n), due to the storage of the modified word each step.
By conceptualizing the problem as a cyclic permutation, this approach identifies the minimum number of rotations through string matching. By checking each possible rotated version of the word, it determines when the initial state reappears. This is more efficient than pure simulation.
This C++ function constructs an extended version of the original word by concatenating it with itself. It then checks each segment of this double string to see if it matches the original word. The first index where this occurs (considering the cyclic shifts by k) is returned.
C#
Time Complexity: O(n^2), as it checks each cyclic permutation.
Space Complexity: O(n), for the double-sized storage of the word.
| Approach | Complexity |
|---|---|
| Simulation and State Tracking | Time Complexity: O(n2) where n is the length of the word, owing to repeated string operations. Space Complexity: O(n) for storing intermediate string states. |
| Loop Detection by Cycle Length | Time Complexity: O(log(n+k)) due to the GCD calculation. Space Complexity: O(1) since it only utilizes a constant amount of additional space. |
| Brute Force Simulation | Time Complexity: O(n), where n is the length of the word. |
| Cyclic Permutation Check | Time Complexity: O(n^2), as it checks each cyclic permutation. |
3031. Minimum Time to Revert Word to Initial State II | KMP | Weekly Contest 383 | String Matching • Aryan Mittal • 4,835 views views
Watch 9 more video solutions →Practice Minimum Time to Revert Word to Initial State I with our built-in code editor and test cases.
Practice on FleetCode