3031. Minimum Time to Revert Word II - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 <= 10⁶
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.

Python

def min_time_to_revert(word: str, k: int) -> int:
    n = len(word)
    temp = word
    time = 0
    while True:
        time += 1
        temp = temp[k:] + temp[:k]
        if temp == word:
            return time

word = "abacaba"
k = 3
print(min_time_to_revert(word, k))  # Output: 2

Java

public class Main {
    public static int minTimeToRevert(String word, int k) {
        int n = word.length();
        String temp = word;
        int time = 0;
        do {
            time++;
            temp = temp.substring(k) + temp.substring(0, k);
        } while (!temp.equals(word));
        return time;
    }

    public static void main(String[] args) {
        String word = "abacaba";
        int k = 3;
        System.out.println(minTimeToRevert(word, k)); // Output: 2
    }
}

C++

#include <iostream>
#include <string>

int minTimeToRevert(std::string word, int k) {
    int n = word.length();
    std::string temp = word;
    for (int time = 1;; time++) {
        std::string rotated = temp.substr(k) + temp.substr(0, k);
        if (rotated == word) {
            return time;
        }
        temp = rotated;
    }
    return -1; // Should not reach here theoretically
}

int main() {
    std::string word = "abacaba";
    int k = 3;
    std::cout << minTimeToRevert(word, k) << std::endl; // Output: 2
    return 0;
}

JavaScript

function minTimeToRevert(word, k) {
    let n = word.length;
    let temp = word;
    let time = 0;
    while (true) {
        time++;
        temp = temp.substring(k) + temp.substring(0, k);
        if (temp === word) {
            return time;
        }
    }
}

let word = "abacaba";
let k = 3;
console.log(minTimeToRevert(word, k)); // Output: 2

#include <stdio.h>
#include <string.h>

int minTimeToRevert(char *word, int k) {
    int n = strlen(word);
    char temp[n + 1];
    strcpy(temp, word);
    for (int time = 1;; time++) {
        char rotated[n + 1];
        strncpy(rotated, &temp[k], n - k);
        strncpy(&rotated[n - k], temp, k);
        rotated[n] = '\0';
        if (strcmp(word, rotated) == 0) {
            return time;
        }
        strcpy(temp, rotated);
    }
}

int main() {
    char word[] = "abacaba";
    int k = 3;
    printf("%d\n", minTimeToRevert(word, k)); // Output: 2
    return 0;
}

using System;
class Program {
    static int MinTimeToRevert(string word, int k) {
        int n = word.Length;
        string temp = word;
        int time = 0;
        do {
            time++;
            temp = temp.Substring(k) + temp.Substring(0, k);
        } while (!temp.Equals(word));
        return time;
    }

    static void Main() {
        string word = "abacaba";
        int k = 3;
        Console.WriteLine(MinTimeToRevert(word, k)); // Output: 2
    }
}

This Python solution also simulates the step-by-step operations. String slicing is used to achieve the desired rotation, and a loop checks when the rotated string equals the original.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n) for intermediate string storage.

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.

Python

import math

def min_time_to_revert(word: str, k: int) -> int:
    n = len(word)
    return n // math.gcd(n, k)

word = "abacaba"
k = 3
print(min_time_to_revert(word, k))  # Output: 2

Java

public class Main {
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static int minTimeToRevert(String word, int k) {
        int n = word.length();
        return n / gcd(n, k);
    }

    public static void main(String[] args) {
        String word = "abacaba";
        int k = 3;
        System.out.println(minTimeToRevert(word, k)); // Output: 2
    }
}

C++

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int minTimeToRevert(string word, int k) {
    int n = word.length();
    return n / gcd(n, k);
}

int main() {
    string word = "abacaba";
    int k = 3;
    cout << minTimeToRevert(word, k) << endl; // Output: 2
    return 0;
}

JavaScript

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function minTimeToRevert(word, k) {
    const n = word.length;
    return n / gcd(n, k);
}

const word = "abacaba";
const k = 3;
console.log(minTimeToRevert(word, k)); // Output: 2

#include <stdio.h>
#include <string.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int minTimeToRevert(char *word, int k) {
    int n = strlen(word);
    int g = gcd(n, k);
    return n / g;
}

int main() {
    char word[] = "abacaba";
    int k = 3;
    printf("%d\n", minTimeToRevert(word, k)); // Output: 2
    return 0;
}

using System;
class Program {
    static int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }

    static int MinTimeToRevert(string word, int k) {
        int n = word.Length;
        return n / Gcd(n, k);
    }

    static void Main() {
        string word = "abacaba";
        int k = 3;
        Console.WriteLine(MinTimeToRevert(word, k)); // Output: 2
    }
}

This Python solution leverages the math.gcd function to find the minimal time through which the initial state will repeat, based on the properties of cyclic permutations.

Complexity

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

Try this approach in the editor

Approach 3: Default Approach

type Hashing struct {
	p   []int64
	h   []int64
	mod int64
}

func NewHashing(word string, base int64, mod int64) *Hashing {
	n := len(word)
	p := make([]int64, n+1)
	h := make([]int64, n+1)
	p[0] = 1
	for i := 1; i <= n; i++ {
		p[i] = (p[i-1] * base) % mod
		h[i] = (h[i-1]*base + int64(word[i-1]-'a')) % mod
	}
	return &Hashing{p, h, mod}
}

func (hashing *Hashing) Query(l, r int) int64 {
	return (hashing.h[r] - hashing.h[l-1]*hashing.p[r-l+1]%hashing.mod + hashing.mod) % hashing.mod
}

func minimumTimeToInitialState(word string, k int) int {
	hashing := NewHashing(word, 13331, 998244353)
	n := len(word)
	for i := k; i < n; i += k {
		if hashing.Query(1, n-i) == hashing.Query(i+1, n) {
			return i / k
		}
	}
	return (n + k - 1) / k
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Full Simulation with String Rotation	Time Complexity: `O(n^2)` Space Complexity: `O(n)` for intermediate string storage.
Optimized Searching for Cycles	Time Complexity: `O(log(min(n, k)))` Space Complexity: `O(1)`
Default Approach	–

Complexity analysis

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

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.

Minimum Time to Revert Word to Initial State II solution and explanation

The problem

Approach overview

Approach 1: Full Simulation with String Rotation

Approach 2: Optimized Searching for Cycles

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Time to Revert Word to Initial State II solution and explanation

The problem

Approach overview

Approach 1: Full Simulation with String Rotation

Approach 2: Optimized Searching for Cycles

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems