Minimum Time to Revert Word to Initial State I - Solution & Explanation
Problem Statement
You are given a 0-indexed string word and an integer k.
At every second, you must perform the following operations:
- Remove the first
kcharacters ofword. - Add any
kcharacters to the end ofword.
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 <= 501 <= k <= word.lengthwordconsists only of lowercase English letters.
Approach Overview
Problem Overview: You start with a string word. Every second, remove the first k characters and append any k characters to the end. The task is to find the minimum number of seconds required for the string to become exactly the original word again.
Approach 1: Simulation and State Tracking (O(n^2) time, O(1) space)
Think about what the string looks like after each second. Removing the first k characters shifts the remaining substring left. To match the original word again, the remaining suffix must equal the prefix of the original word. For time t, we effectively remove t * k characters from the front. Check whether word[t*k:] matches word[:n - t*k]. If it does, you can append characters that complete the string to exactly match the original. Iterate over multiples of k until you find the first valid match.
This approach directly compares substrings using basic string operations. Each comparison can take O(n), and there may be up to n/k checks, giving O(n^2) in the worst case. It’s straightforward and easy to implement but inefficient for larger inputs.
Approach 2: Loop Detection by Cycle Length (O(n) time, O(n) space)
Instead of repeatedly comparing substrings, treat the process as checking valid prefix–suffix alignments. After removing t*k characters, the remaining suffix must equal the prefix of the original word. This is a classic string matching problem. Precompute prefix matches using techniques like the Z-array or a rolling hash. Then check candidate positions k, 2k, 3k, ... to see if the suffix starting there matches the prefix.
Because prefix matches are precomputed in linear time, each check becomes O(1). This reduces the full process to O(n) time with O(n) auxiliary memory. The key insight: you never need to simulate character appends. Only verify whether the remaining substring already matches the required prefix.
Recommended for interviews: Start by describing the simulation idea since it shows clear understanding of the transformation process. Then optimize using prefix matching or rolling hash to avoid repeated substring comparisons. Interviewers typically expect the linear-time string matching solution because it demonstrates familiarity with efficient pattern-matching techniques.
Approach 1: Simulation and State Tracking
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.
Complexity
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.
Approach 2: Loop Detection by Cycle Length
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.
Complexity
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.
Approach 3: Brute Force Simulation
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.
Code
Python
JavaScript
Complexity
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.
Approach 4: Cyclic Permutation Check
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.
Complexity
Time Complexity: O(n^2), as it checks each cyclic permutation.
Space Complexity: O(n), for the double-sized storage of the word.
Approach 5: 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].
If there are multiple operations, let's assume i is the number of operations, then it means that word[k*i:] is a prefix of word, i.e., word[k*i:] == word[:n-k*i].
Therefore, we can enumerate the number of operations and check whether word[k*i:] is a prefix of word. If it is, then return i.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of word.
Code
Python
Java
C++
Go
TypeScript
Approach 6: Enumeration + String Hash
Based on Solution 1, we can also use string hashing to determine whether two strings are equal.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of word.
Complexity Comparison
| 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. |
| Enumeration | — |
| Enumeration + String Hash | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation and State Tracking | O(n^2) | O(1) | Simple implementation when constraints are small or when demonstrating the basic idea first |
| Loop Detection by Cycle Length (Prefix/Suffix Matching) | O(n) | O(n) | Preferred solution for large inputs using prefix matching or rolling hash |
Video Solution
Minimum Time to Revert Word to Initial State | Part I | Part II | KMP | Leetcode 3029 | 3031 • codestorywithMIK • 4,746 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Minimum Time to Revert Word to Initial State I easy or hard?
Minimum Time to Revert Word to Initial State I Python/Java solution
How to solve Minimum Time to Revert Word to Initial State I in O(n)?
What is the best approach for Minimum Time to Revert Word to Initial State I?
Is Minimum Time to Revert Word to Initial State I asked at Google/Amazon/Meta?
What data structure is used in Minimum Time to Revert Word to Initial State I?
What is the time complexity of Minimum Time to Revert Word to Initial State I?
Ready to solve this problem?
Practice Minimum Time to Revert Word to Initial State I with our built-in code editor and test cases.
Practice on FleetCode