3029. Minimum Time to Revert Word to Initial State I - Solution

Q: Is Minimum Time to Revert Word to Initial State I easy or hard?

The problem is rated Medium because the brute-force idea is simple but inefficient. Achieving the optimal solution requires recognizing the prefix–suffix matching pattern and applying a linear-time string matching technique.

Q: Minimum Time to Revert Word to Initial State I Python/Java solution

Both Python and Java implementations follow the same logic: iterate over multiples of k and check whether the remaining substring matches the original prefix. Optimized solutions use a precomputed Z-array or rolling hash to perform substring comparisons in constant time.

Q: How to solve Minimum Time to Revert Word to Initial State I in O(n)?

Precompute prefix matches using a string matching algorithm such as the Z-array or rolling hash. Then iterate through positions k, 2k, 3k, and check whether the suffix starting at that index matches the prefix of the word. The first match determines the minimum number of seconds.

Q: What is the best approach for Minimum Time to Revert Word to Initial State I?

The most efficient approach checks prefix–suffix matches at multiples of k using string matching techniques such as the Z algorithm or rolling hash. Precomputing prefix matches allows each candidate position to be verified in O(1), resulting in an overall O(n) time solution with O(n) space.

Q: Is Minimum Time to Revert Word to Initial State I asked at Google/Amazon/Meta?

Problems involving prefix–suffix matching and rolling hash techniques appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying pattern—efficient string matching—is commonly tested.

Q: What data structure is used in Minimum Time to Revert Word to Initial State I?

The solution mainly relies on string processing techniques rather than complex data structures. Efficient implementations often use prefix arrays such as the Z-array or polynomial rolling hash tables to compare substrings quickly.

Q: What is the time complexity of Minimum Time to Revert Word to Initial State I?

The straightforward simulation approach takes O(n^2) time because substring comparisons may run in O(n) and occur up to n/k times. Using prefix matching or rolling hash reduces the complexity to O(n) time with O(n) auxiliary space.

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 <= 50
1 <= k <= word.length
word consists 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.

Python

def min_time_to_revert(word, k):
    original = word
    time = 0
    while True:
        first_part = word[:k]
        word = word[k:] + first_part
        time += 1
        if word == original:
            return time

word = "abacaba"
k = 3
print(min_time_to_revert(word, k))

Java

public class RevertWord {
    public static int minTimeToRevert(String word, int k) {
        String original = word;
        int len = word.length();
        int time = 0;
        do {
            String firstPart = word.substring(0, k);
            word = word.substring(k) + firstPart;
            time++;
        } while (!word.equals(original));
        return time;
    }

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

C++

#include <iostream>
#include <string>

int minTimeToRevert(std::string word, int k) {
    std::string original = word;
    int time = 0;
    do {
        std::string firstPart = word.substr(0, k);
        word = word.substr(k) + firstPart;
        time++;
    } while (word != original);
    return time;
}

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

JavaScript

function minTimeToRevert(word, k) {
    let original = word;
    let time = 0;
    do {
        let firstPart = word.substring(0, k);
        word = word.substr(k) + firstPart;
        time++;
    } while (word !== original);
    return time;
}

const word = "abacaba";
const k = 3;
console.log(minTimeToRevert(word, k));

#include <stdio.h>
#include <string.h>
bool is_reverted(const char* word, const char* current, int n) {
    return strncmp(word, current, n) == 0;
}

int min_time_to_revert(char* word, int k) {
    int len = strlen(word);
    char current[51];
    strncpy(current, word, len);
    int time = 0;
    do {
        char removed[51], added[51];
        strncpy(removed, current, k);
        strcpy(added, current + k);
        strcat(added, removed);
        strcpy(current, added);
        time++;
    } while(!is_reverted(word, current, len));
    return time;
}

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

using System;

class Program {
    static int MinTimeToRevert(string word, int k) {
        string original = word;
        int len = word.Length;
        int time = 0;
        do {
            string firstPart = word.Substring(0, k);
            word = word.Substring(k) + firstPart;
            time++;
        } while (word != original);
        return time;
    }

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

Python implements the logic of slicing the first k characters, appending them to the end, and checking each state for a match with the original. It returns the count of operations needed.

Complexity

Time Complexity: O(n*m) because of the slicing operations. Space Complexity: O(n) for storing multiple states of the string during execution.

Try this approach in the editor

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).

Python

import math

def min_time_to_revert(word_length, k):
    return word_length // math.gcd(word_length, k)

word_length = 7  # e.g., 'abacaba'.
k = 3
print(min_time_to_revert(word_length, k))

Java

public class RevertWord {
    public static int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
    
    public static int minTimeToRevert(int wordLength, int k) {
        return wordLength / gcd(wordLength, k);
    }

    public static void main(String[] args) {
        int lengthOfWord = 7;
        int k = 3;
        System.out.println(minTimeToRevert(lengthOfWord, k));
    }
}

C++

#include <iostream>

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

int minTimeToRevert(int n, int k) {
    return n / gcd(n, k);
}

int main() {
    int length_of_word = 7;
    int k = 3;
    std::cout << minTimeToRevert(length_of_word, k) << std::endl;
    return 0;
}

JavaScript

function gcd(a, b) {
    while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
    }
    return a;
}

function minTimeToRevert(wordLength, k) {
    return wordLength / gcd(wordLength, k);
}

const wordLength = 7;
const k = 3;
console.log(minTimeToRevert(wordLength, k));

#include <stdio.h>

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

int min_time_to_revert(int n, int k) {
    return n / gcd(n, k);
}

int main() {
    int length_of_word = 7; // e.g., "abacaba" is 7 characters long
    int k = 3;
    printf("%d\n", min_time_to_revert(length_of_word, k));
    return 0;
}

using System;

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

    static int MinTimeToRevert(int lengthOfWord, int k) {
        return lengthOfWord / GCD(lengthOfWord, k);
    }

    static void Main() {
        int lengthOfWord = 7;
        int k = 3;
        Console.WriteLine(MinTimeToRevert(lengthOfWord, k));
    }
}

This Python function utilizes the built-in gcd function to derive the shift factor necessary for the original configuration to come back, using modular cycle calculations.

Complexity

Time Complexity: O(log(n+k)). Space Complexity: O(1) due to space constraints restricted to linear storage nodes.

Try this approach in the editor

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.

Python

def min_time_to_revert(word, k):
    initial = word
    count = 0
    while True:
        count += 1
        word = word[k:] + word[:k]
        if word == initial:
            return count

JavaScript

function minTimeToRevert(word, k) {
    const initial = word;
    let count = 0;
    while (true) {
        count++;
        word = word.slice(k) + word.slice(0, k);
        if (word === initial) {
            return count;
        }
    }
}

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.

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.

Try this approach in the editor

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.

C++

#include <iostream>
#include <string>

int minTimeToRevert(const std::string& word, int k) {
    std::string extended = word + word;
    int len = word.size();
    for (int i = 1; i < len; ++i) {
        if (word == extended.substr(i * k % len, len)) {
            return i;
        }
    }
    return len;
}

using System;

public class Solution {
    public int MinTimeToRevert(string word, int k) {
        string doubled = word + word;
        for (int i = 1; i < word.Length; i++) {
            if (doubled.Substring(i * k % word.Length, word.Length) == word) {
                return i;
            }
        }
        return word.Length;
    }
}

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.

Try this approach in the editor

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.

TypeScript

function minimumTimeToInitialState(word: string, k: number): number {
    const n = word.length;
    for (let i = k; i < n; i += k) {
        if (word.slice(i) === word.slice(0, -i)) {
            return Math.floor(i / k);
        }
    }
    return Math.floor((n + k - 1) / k);
}

func minimumTimeToInitialState(word string, k int) int {
	n := len(word)
	for i := k; i < n; i += k {
		if word[i:] == word[:n-i] {
			return i / k
		}
	}
	return (n + k - 1) / k
}

Try this approach in the editor

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.

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
Simulation and State Tracking	Time Complexity: O(n*m) because of the slicing operations. Space Complexity: O(n) for storing multiple states of the string during execution.
Loop Detection by Cycle Length	Time Complexity: O(log(n+k)). Space Complexity: O(1) due to space constraints restricted to linear storage nodes.
Brute Force Simulation	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.
Cyclic Permutation Check	Time Complexity: O(n^2), as it checks each cyclic permutation. Space Complexity: O(n), for the double-sized storage of the word.
Enumeration	–
Enumeration + String Hash	–

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

Frequently asked questions

Is Minimum Time to Revert Word to Initial State I easy or hard?

The problem is rated Medium because the brute-force idea is simple but inefficient. Achieving the optimal solution requires recognizing the prefix–suffix matching pattern and applying a linear-time string matching technique.

Minimum Time to Revert Word to Initial State I Python/Java solution

Both Python and Java implementations follow the same logic: iterate over multiples of k and check whether the remaining substring matches the original prefix. Optimized solutions use a precomputed Z-array or rolling hash to perform substring comparisons in constant time.

How to solve Minimum Time to Revert Word to Initial State I in O(n)?

Precompute prefix matches using a string matching algorithm such as the Z-array or rolling hash. Then iterate through positions k, 2k, 3k, and check whether the suffix starting at that index matches the prefix of the word. The first match determines the minimum number of seconds.

What is the best approach for Minimum Time to Revert Word to Initial State I?

The most efficient approach checks prefix–suffix matches at multiples of k using string matching techniques such as the Z algorithm or rolling hash. Precomputing prefix matches allows each candidate position to be verified in O(1), resulting in an overall O(n) time solution with O(n) space.

Is Minimum Time to Revert Word to Initial State I asked at Google/Amazon/Meta?

Problems involving prefix–suffix matching and rolling hash techniques appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying pattern—efficient string matching—is commonly tested.

What data structure is used in Minimum Time to Revert Word to Initial State I?

The solution mainly relies on string processing techniques rather than complex data structures. Efficient implementations often use prefix arrays such as the Z-array or polynomial rolling hash tables to compare substrings quickly.

What is the time complexity of Minimum Time to Revert Word to Initial State I?

The straightforward simulation approach takes O(n^2) time because substring comparisons may run in O(n) and occur up to n/k times. Using prefix matching or rolling hash reduces the complexity to O(n) time with O(n) auxiliary space.

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

The problem

Approach overview

Approach 1: Simulation and State Tracking

Approach 2: Loop Detection by Cycle Length

Approach 3: Brute Force Simulation

Approach 4: Cyclic Permutation Check

Approach 5: Enumeration

Approach 6: Enumeration + String Hash

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

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

The problem

Approach overview

Approach 1: Simulation and State Tracking

Approach 2: Loop Detection by Cycle Length

Approach 3: Brute Force Simulation

Approach 4: Cyclic Permutation Check

Approach 5: Enumeration

Approach 6: Enumeration + String Hash

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems