# Minimum Time to Revert Word to Initial State II
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-time-to-revert-word-to-initial-state-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-revert-word-to-initial-state-ii
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## 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 <= 106`
* `1 <= k <= word.length`
* `word` consists only of lowercase English letters.

# Approaches
## Brute Force with String Comparison
This approach directly simulates the process described in the problem. We iterate through the number of operations `t` starting from 1. For each `t`, we calculate the number of characters removed from the prefix, which is `i = t * k`. We then check if the remaining suffix of the original word, `word.substring(i)`, is identical to a prefix of the original word of the same length, `word.substring(0, n-i)`. If they match, we've found the minimum time `t`. If we iterate through all possible `t` where `t*k < n` and find no match, the answer is the smallest `t` for which `t*k >= n`, which is `ceil(n/k)`.
**Time:** O(N^2 / k). The loop for `t` runs up to `N/k` times. In each iteration, we compare strings of length `N - t*k`. The total number of character comparisons is the sum `(N-k) + (N-2k) + ...`, which is on the order of `O(N^2 / k)`. In the worst case, when `k=1`, the complexity is `O(N^2)`. · **Space:** O(1). We are not using any extra space that scales with the input size `n`. `regionMatches` compares parts of the existing string in-place.
**Pros:** Simple to understand and implement.; It correctly solves the problem for small inputs.
**Cons:** The time complexity is high, making it unsuitable for large constraints.; It will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
The core idea is to test each possible time `t=1, 2, 3, ...` sequentially. For a given time `t`, `t*k` characters are removed from the beginning of the word. The length of the word is `n`. The remaining part of the word is the suffix starting at index `t*k`, and its length is `n - t*k`. To revert to the initial state, this remaining suffix must be a prefix of the original word. So, we check if `word[i...n-1]` equals `word[0...n-i-1]`. The first `t > 0` for which this condition holds is our answer. If no such `t` exists for `t*k < n`, it means we can only revert the word after removing all of its characters. The time for this is `ceil(n/k)`, which can be calculated using integer arithmetic as `(n + k - 1) / k`. The loop for `t` will naturally arrive at this value if no earlier match is found.

```java
class Solution {
    public int minimumTimeToInitialState(String word, int k) {
        int n = word.length();
        for (int t = 1; ; ++t) {
            int i = t * k;
            if (i >= n) {
                return t;
            }
            // Check if suffix starting at i matches prefix of same length
            if (word.regionMatches(0, word, i, n - i)) {
                return t;
            }
        }
    }
}
```
### Algorithm
1. Get the length of the word, `n`.
2. Loop through time `t` starting from 1.
3. In each iteration, calculate the number of characters that would have been removed, `i = t * k`.
4. If `i` is greater than or equal to `n`, it means we have checked all possibilities where a non-empty suffix of the original word remains. The minimum time is `t` in this case, so we return `t`.
5. Otherwise, we check if the suffix of `word` starting at index `i` is equal to the prefix of `word` of the same length (`n-i`). We can use `word.regionMatches(0, word, i, n - i)` for an efficient comparison that avoids creating new string objects.
6. If they are equal, we have found the smallest `t` that works, so we return `t`.
7. If the strings are not equal, we continue to the next value of `t`.

## Optimized Check with Z-Algorithm
The brute-force approach is slow because of the repeated string comparisons inside the loop. We can significantly optimize this check using a standard string algorithm. The Z-algorithm is perfectly suited for this task. It preprocesses the string `word` in `O(n)` time to create a Z-array. The value `z[i]` in this array stores the length of the longest common prefix between `word` and the suffix of `word` starting at index `i`. This allows us to check our condition in `O(1)` time.
**Time:** O(N). Computing the Z-array takes `O(N)`. The subsequent loop runs at most `N/k` times, and each check inside the loop is an `O(1)` array lookup. The total time is `O(N + N/k) = O(N)`. · **Space:** O(N) to store the Z-array.
**Pros:** Highly efficient with a linear time complexity.; Guaranteed to pass within the time limits for large inputs.
**Cons:** Requires knowledge of the Z-algorithm, which is a non-trivial string algorithm.; The implementation of the Z-algorithm can be tricky to get right.
### Explanation
The condition we need to check for each potential time `t` is whether the suffix `word.substring(t*k)` is a prefix of the original `word`. Let `i = t*k`. This is equivalent to checking if the Longest Common Prefix (LCP) of `word` and `word.substring(i)` has a length of at least `n-i` (the length of the suffix). The Z-array gives us this information directly: `z[i]` is the length of the LCP of `word` and `word.substring(i)`. Therefore, the check simplifies to `z[i] >= n - i`.

By precomputing the Z-array for the entire `word`, we can then iterate through the relevant indices `i = k, 2k, 3k, ...` and perform this check in constant time for each.

```java
class Solution {
    public int minimumTimeToInitialState(String word, int k) {
        int n = word.length();
        int[] z = new int[n];
        // Z-algorithm to compute the Z-array
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && word.charAt(z[i]) == word.charAt(i + z[i])) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }

        for (int t = 1; ; ++t) {
            int i = t * k;
            if (i >= n) {
                return t;
            }
            if (z[i] >= n - i) {
                return t;
            }
        }
    }
}
```
### Algorithm
1. First, compute the Z-array for the input `word`. The Z-algorithm builds this array in `O(n)` time.
2. Iterate `t` from 1 upwards. Let `i = t * k` be the starting index of the suffix.
3. If `i >= n`, it means we have checked all valid `t` where a non-empty suffix could match a prefix. The answer is the current `t`. Return `t`.
4. For the current index `i`, check the precomputed Z-value `z[i]`. The condition `word.substring(i)` is a prefix of `word` is equivalent to `z[i] >= n - i`.
5. If `z[i] >= n - i`, the condition is met. We have found the minimum time `t = i/k`. Return `t`.
6. If the condition is not met, continue to the next multiple of `k`.

## Optimized Search with KMP's LPS Array
This approach reframes the problem in a way that perfectly aligns with the strengths of the Knuth-Morris-Pratt (KMP) algorithm's preprocessing step. We are looking for a state where the remaining suffix is also a prefix of the original word. This is equivalent to finding a prefix of `word` that is also a suffix of `word`. Let the length of such a prefix-suffix be `L`. The number of characters removed to reach this state is `n-L`. For this to be an achievable state, `n-L` must be a multiple of `k`. To find the *minimum* time `t = (n-L)/k`, we need to find the *maximum* possible `L` that satisfies this divisibility condition.
**Time:** O(N). Computing the LPS array takes `O(N)`. The subsequent `while` loop to check lengths also takes at most `O(N)` in total over all its iterations, as `len` is strictly decreasing. · **Space:** O(N) to store the LPS array.
**Pros:** Very efficient, with linear time complexity.; The logic is elegant and directly tackles the core structure of the problem (prefix-suffixes).; Potentially faster in practice than the Z-algorithm approach as it only checks lengths that are valid prefix-suffixes, which are often sparse.
**Cons:** Requires knowledge of the KMP algorithm's preprocessing step (LPS array construction).; The logic, while elegant, might be slightly less direct to derive compared to the Z-algorithm approach.
### Explanation
The KMP preprocessing algorithm computes an LPS (Longest Proper Prefix Suffix) array. For a string `S`, `lps[i]` stores the length of the longest proper prefix of `S[0...i]` that is also a suffix of `S[0...i]`. The key insight is that all prefixes of `word` that are also suffixes can be found by starting with the longest one, `L = lps[n-1]`, and then repeatedly chaining back via `L = lps[L-1]` until `L` becomes 0. We can iterate through this chain of lengths from longest to shortest, and the first one we find that satisfies `(n - L) % k == 0` will give us our answer.

```java
class Solution {
    public int minimumTimeToInitialState(String word, int k) {
        int n = word.length();
        int[] lps = new int[n];
        // KMP preprocessing to compute LPS array
        int length = 0;
        for (int i = 1; i < n; i++) {
            while (length > 0 && word.charAt(i) != word.charAt(length)) {
                length = lps[length - 1];
            }
            if (word.charAt(i) == word.charAt(length)) {
                length++;
            }
            lps[i] = length;
        }

        int len = lps[n - 1];
        while (len > 0) {
            if ((n - len) % k == 0) {
                return (n - len) / k;
            }
            len = lps[len - 1];
        }

        // If no such prefix-suffix works, we must remove chunks until the word is empty.
        return (n + k - 1) / k;
    }
}
```
### Algorithm
1. Compute the Longest Proper Prefix Suffix (LPS) array for `word` using the KMP preprocessing algorithm. This takes `O(n)` time.
2. Find the length of the longest proper prefix of `word` that is also a suffix. This is given by `L = lps[n-1]`.
3. Start a loop with the current length `L`. While `L > 0`:
    a. Check if the number of removed characters, `n - L`, is divisible by `k`.
    b. If `(n - L) % k == 0`, we have found the largest `L` that works. This corresponds to the minimum time `t = (n - L) / k`. Return this value.
    c. If not divisible, find the next longest prefix-suffix by updating `L` to `lps[L-1]` and continue the loop.
4. If the loop finishes (meaning `L` becomes 0), no non-empty prefix-suffix satisfies the condition. The only way to revert is to remove characters until the word is empty. The time required is `ceil(n/k)`, which is `(n + k - 1) / k`. Return this value.

# Solutions
### Java

```java
class Hashing { private final long [] p ; private final long [] h ; private final long mod ; public Hashing ( String word , long base , int mod ) { int n = word . length (); p = new long [ n + 1 ]; h = new long [ n + 1 ]; p [ 0 ] = 1 ; this . mod = mod ; for ( int i = 1 ; i <= n ; i ++) { p [ i ] = p [ i - 1 ] * base % mod ; h [ i ] = ( h [ i - 1 ] * base + word . charAt ( i - 1 ) - 'a' ) % mod ; } } public long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } } class Solution { public int minimumTimeToInitialState ( String word , int k ) { Hashing hashing = new Hashing ( word , 13331 , 998244353 ); int n = word . length (); for ( int 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 ; } }
```

### CPP

```cpp
class Hashing { private: vector < long long > p ; vector < long long > h ; long long mod ; public: Hashing ( string word , long long base , int mod ) { int n = word . size (); p . resize ( n + 1 ); h . resize ( n + 1 ); p [ 0 ] = 1 ; this -> mod = mod ; for ( int i = 1 ; i <= n ; i ++ ) { p [ i ] = ( p [ i - 1 ] * base ) % mod ; h [ i ] = ( h [ i - 1 ] * base + word [ i - 1 ] - 'a' ) % mod ; } } long long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } }; class Solution { public: int minimumTimeToInitialState ( string word , int k ) { Hashing hashing ( word , 13331 , 998244353 ); int n = word . size (); for ( int 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 ; } };
```

### Python

```python
class Hashing : __slots__ = [ "mod" , "h" , "p" ] def __init__ ( self , s : str , base : int , mod : int ): self . mod = mod self . h = [ 0 ] * ( len ( s ) + 1 ) self . p = [ 1 ] * ( len ( s ) + 1 ) for i in range ( 1 , len ( s ) + 1 ): self . h [ i ] = ( self . h [ i - 1 ] * base + ord ( s [ i - 1 ])) % mod self . p [ i ] = ( self . p [ i - 1 ] * base ) % mod def query ( self , l : int , r : int ) -> int : return ( self . h [ r ] - self . h [ l - 1 ] * self . p [ r - l + 1 ]) % self . mod class Solution : def minimumTimeToInitialState ( self , word : str , k : int ) -> int : hashing = Hashing ( word , 13331 , 998244353 ) n = len ( word ) for i in range ( k , n , k ): if hashing . query ( 1 , n - i ) == hashing . query ( i + 1 , n ): return i // k return ( n + k - 1 ) // k
```