Skip to main content
Talentd

Minimum Time to Revert Word to Initial State II - Solution & Explanation

HardStringRolling HashString MatchingHash Function15 min readAsked at: Sprinklr
Practice this problem

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 k characters of word.
  • Add any 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 <= 106
  • 1 <= k <= word.length
  • word consists only of lowercase English letters.

Approach Overview

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 1: Full Simulation with String Rotation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to repeated rotations of strings of length n.
Space Complexity: O(n) for the temporary storage of strings.

Try this approach in the editor →

Approach 2: Optimized Searching for Cycles

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(min(n, k)))
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Full Simulation with String Rotation

Time Complexity: O(n^2) due to repeated rotations of strings of length n.
Space Complexity: O(n) for the temporary storage of strings.

Optimized Searching for Cycles

Time Complexity: O(log(min(n, k)))
Space Complexity: O(1)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Full Simulation with String RotationO(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

Video Solution

3031. Minimum Time to Revert Word to Initial State II | KMP | Weekly Contest 383 | String Matching • Aryan Mittal • 5,324 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Time to Revert Word to Initial State II easy or hard?
Minimum Time to Revert Word to Initial State II is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the prefix-suffix cycle pattern and applying efficient string matching instead of brute-force simulation.
Minimum Time to Revert Word to Initial State II Python/Java solution
Python, Java, C++, and other languages can implement the optimized solution by checking prefix-suffix matches at multiples of k. Many implementations use rolling hash or direct substring comparison with precomputed hashes to maintain O(n) complexity.
How to solve Minimum Time to Revert Word to Initial State II in O(n)?
Iterate over indices i = k, 2k, 3k, ... and check if word[i:] equals word[:n-i]. Using rolling hash or other substring hashing allows constant-time substring comparison. The first index where the prefix and suffix match determines the minimum time.
What is the best approach for Minimum Time to Revert Word to Initial State II?
The most efficient approach checks when a suffix of the word matches its prefix after shifting by multiples of k. This can be implemented using string matching or rolling hash to compare substrings quickly. The method runs in O(n) time and avoids expensive string reconstruction.
Is Minimum Time to Revert Word to Initial State II asked at Google/Amazon/Meta?
Hard string problems involving substring matching, rolling hash, or prefix-suffix alignment are common in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of string shifts, hashing, and cycle detection patterns.
What data structure is used in Minimum Time to Revert Word to Initial State II?
The solution primarily relies on string processing with techniques like rolling hash or prefix matching. Auxiliary arrays or hash values may be stored to compare substrings efficiently in constant time.
What is the time complexity of Minimum Time to Revert Word to Initial State II?
The optimal solution runs in O(n) time and O(n) space. It iterates through positions that are multiples of k and checks whether the remaining suffix equals the corresponding prefix using hashing or prefix comparison.

Ready to solve this problem?

Practice Minimum Time to Revert Word to Initial State II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Happy Prefix