Watch 9 video solutions for Minimum Time to Revert Word to Initial State I, a medium level problem involving String, Rolling Hash, String Matching. This walkthrough by codestorywithMIK has 4,469 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 <= 50 1 <= k <= word.lengthword consists only of lowercase English letters.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 | 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 |