# Minimum Time to Revert Word to Initial State I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-to-revert-word-to-initial-state-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-revert-word-to-initial-state-i
**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 <= 50 `
* `1 <= k <= word.length`
* `word` consists only of lowercase English letters.

# Approaches
## Iterative Search for Periodic Suffix
This is a straightforward approach that iterates through the possible times `t=1, 2, ...` and for each time, checks if the condition for reverting to the initial state is met. The condition is that a suffix of the original word must match a prefix of the same length.
**Time:** O(N^2 / K), where N is the length of the word. The loop runs up to `O(N/K)` times. In each iteration, creating and comparing substrings of length up to N takes `O(N)` time. · **Space:** O(N) in Java, where N is the length of the word. This is due to the creation of new substring objects in each iteration. If `regionMatches` is used, the space complexity is O(1).
**Pros:** Simple logic that directly translates the problem's core condition.; Easy to implement and understand.; Sufficiently fast for the given constraints (`word.length <= 50`).
**Cons:** Inefficient for very large strings due to repeated substring creation and comparison, leading to a quadratic time complexity in the worst case.
### Explanation
The problem can be rephrased as finding the smallest integer `t > 0` such that `word` has a period of `p = t * k`. A string `s` of length `n` has a period `p` if its prefix of length `n-p` is equal to its suffix of length `n-p` (which starts at index `p`).

We can iterate `t` starting from 1. For each `t`, we calculate the potential period `p = t * k`.

We only need to check for `p < n`. If `p >= n`, it means we have conceptually removed at least `n` characters. In this scenario, we can always reconstruct the original word. The minimum time `t` for this to happen is `ceil(n/k)`.

For each `t` where `p = t*k < n`, we check if `word.substring(0, n - p)` is equal to `word.substring(p)`.

The first `t` that satisfies this condition is the minimum time required, so we return it.

If the loop finishes without finding such a `t`, it means no period `t*k` exists for `t*k < n`. The answer is then `ceil(n/k)`.

```java
class Solution {
    public int minimumTimeToInitialState(String word, int k) {
        int n = word.length();
        for (int t = 1; t * k < n; ++t) {
            int p = t * k;
            // Check if word has period p.
            // This is equivalent to checking if the suffix of length n-p
            // is equal to the prefix of length n-p.
            // The suffix starts at index p.
            if (word.substring(p).equals(word.substring(0, n - p))) {
                return t;
            }
        }
        // If no such shorter period is found, the answer is the time
        // needed to remove at least n characters.
        return (n + k - 1) / k;
    }
}
```

A small optimization is to use `word.regionMatches()` to avoid creating new substring objects, which can be more efficient.

```java
// Alternative check inside the loop
// if (word.regionMatches(0, word, p, n - p)) {
//     return t;
// }
```
### Algorithm
*   1.  Get the length of the word, `n`.
*   2.  Start a loop for time `t` from 1. The loop should continue as long as `t * k < n`.
*   3.  Inside the loop, calculate the number of characters removed, `p = t * k`.
*   4.  Check if the prefix of `word` of length `n-p` is equal to the suffix of `word` starting at index `p`. This can be done using string slicing and comparison.
*   5.  If they are equal, it means we can revert the word to its initial state. Return the current time `t` as it's the minimum.
*   6.  If the loop completes without finding such a `t`, it means no period `t*k` exists for `t*k < n`. The answer is then the smallest `t` such that `t*k >= n`, which is `ceil(n/k)`. Return `(n + k - 1) / k`.

## Optimized Search using KMP's Prefix Function
This approach improves upon the iterative search by using an advanced string algorithm, the Knuth-Morris-Pratt (KMP) algorithm's prefix function (LPS array). This allows us to find all possible periods of the string efficiently after a single linear-time scan, leading to a more optimal overall solution.
**Time:** O(N), where N is the length of the word. The LPS array computation takes O(N), and the subsequent search for the correct border also takes at most O(N). · **Space:** O(N) to store the LPS array.
**Pros:** Highly efficient with a linear time complexity.; It is a deterministic approach, unlike hashing-based methods.; Provides the most optimal solution regardless of input size.
**Cons:** The implementation is more complex than the naive approach.; The KMP algorithm itself can be non-trivial to understand and implement correctly.
### Explanation
The problem of finding the minimum time `t` can be reduced to finding the smallest `t > 0` such that `p = t*k` is a period of the `word`. A key insight from stringology is that a string `s` of length `N` has a period `p` if and only if `N-p` is the length of a 'border' (a proper prefix that is also a suffix).

The KMP preprocessing algorithm is designed to find the longest border for every prefix of a string and stores these lengths in an LPS (Longest Proper Prefix Suffix) array. We can compute this array for `word` in `O(N)` time.

Once we have the LPS array, we can find the lengths of all borders of `word`. The longest border has length `L1 = lps[N-1]`. The next longest has length `L2 = lps[L1-1]`, and so on. We are looking for the largest border length `L` such that the corresponding period `p = N-L` is a multiple of `k`. This will give us the smallest `t = p/k`.

We can iterate backwards through the border lengths and test the condition. The first one that satisfies it gives our answer. If no such border works, the only option is to remove characters until the word is empty, which takes `ceil(N/k)` seconds.

```java
class Solution {
    public int minimumTimeToInitialState(String word, int k) {
        int n = word.length();
        int[] lps = computeLPSArray(word);
        
        int longestMatch = lps[n - 1];
        
        // Find the largest border length L such that (n - L) is a multiple of k.
        // This corresponds to the smallest period p = n - L that is a multiple of k.
        while (longestMatch > 0 && (n - longestMatch) % k != 0) {
            longestMatch = lps[longestMatch - 1];
        }
        
        if ((n - longestMatch) % k == 0) {
            return (n - longestMatch) / k;
        }
        
        // If no such border is found, the answer is ceil(n/k).
        return (n + k - 1) / k;
    }

    private int[] computeLPSArray(String s) {
        int n = s.length();
        int[] lps = new int[n];
        for (int i = 1, len = 0; i < n;) {
            if (s.charAt(i) == s.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}
```
### Algorithm
*   1.  Compute the Longest Proper Prefix Suffix (LPS) array for the `word` using the KMP preprocessing algorithm. This takes `O(N)` time.
*   2.  The LPS array helps identify all 'borders' of the string. A string has a period `p` if and only if `N-p` is the length of one of its borders.
*   3.  We need the smallest `t > 0` such that `p = t*k` is a period. This is equivalent to finding the smallest period `p` that is a multiple of `k`.
*   4.  This corresponds to finding the largest border length `L` such that `(N-L)` is a multiple of `k`.
*   5.  Iterate through the border lengths, starting from the longest (`L = lps[N-1]`), then the next longest (`lps[L-1]`), and so on, until a border length `L` is found for which `(N-L)` is divisible by `k`.
*   6.  If such a border `L` is found, the minimum time is `(N-L)/k`.
*   7.  If no such border is found (including the empty border of length 0), the answer is `ceil(N/k)`.

# Solutions
### Python

```python
class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int: n = len(word) for i in range(k, n, k): if word[i:] == word[: - i]: return i // k return (n + k - 1) // k

```

### Java

```java
class Solution {
public
  int minimumTimeToInitialState(String word, int k) {
    int n = word.length();
    for (int i = k; i < n; i += k) {
      if (word.substring(i).equals(word.substring(0, n - i))) {
        return i / k;
      }
    }
    return (n + k - 1) / k;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumTimeToInitialState(string word, int k) {
    int n = word.size();
    for (int i = k; i < n; i += k) {
      if (word.substr(i) == word.substr(0, n - i)) {
        return i / k;
      }
    }
    return (n + k - 1) / k;
  }
};

```