Problem statement

You are given a string word and an integer k.

Every second you must do both of the following:

• remove the first k characters of word, and
• append any k characters of your choice to the end of word.

Return the minimum time greater than zero after which word can be back in its initial state.

This is the large version of the problem: word can hold up to a million characters, so checking each candidate time by comparing strings is too slow.

Example 1

Input: word = "abacaba", k = 3
Output: 2
Explanation: After 2 seconds only the final "a" of the original survives at the front; it is a prefix of "abacaba", so appending "bacaba" restores the word.

Example 2

Input: word = "abababab", k = 3
Output: 2
Explanation: After 1 second "babab" survives, which is not a prefix. After 2 seconds "ab" survives, which is.

Example 3

Input: word = "abcbabcd", k = 2
Output: 4
Explanation: No surviving suffix is ever a prefix, so all 8 characters must be replaced: 4 seconds.

Constraints

• 1 <= word.length <= 10^6
• 1 <= k <= word.length
• word consists only of lowercase English letters

Hints for Minimum Time to Revert Word to Initial State II

1. Hint 1

   After t seconds the word can be the original again exactly when the suffix word[t*k..] is also a prefix of word (or nothing original is left).

2. Hint 2

   So you need, for many positions i, to know whether the suffix starting at i matches the prefix of the same length — the length of the longest common prefix of word and word[i..].

3. Hint 3

   The Z-function gives that length for every i in linear time: z[i] == n - i means the whole suffix is a prefix.

How to solve Minimum Time to Revert Word to Initial State II

The question at time t is whether word[t*k..] is a prefix of word. That is exactly z[t*k] == n - t*k, where z[i] is the longest common prefix of word and its suffix at i — and the Z-function computes all of them in O(n).

Approach

1. Compute the Z-array: keep the rightmost window [l, r) known to match the prefix. For each i, start z[i] at min(r - i, z[i - l]) when i < r, extend it by direct comparison, and move the window if it now reaches further right.
2. For t = 1, 2, …: if t * k >= n return t; if z[t*k] == n - t*k return t.

Why it works

After t seconds the word is word[t*k..] followed by t*k free characters, which can equal the original iff that suffix matches the original's prefix. z[i] == n - i states precisely that the suffix at i matches the prefix along its whole length. Each character extension in the Z loop pushes r right, so the total work is linear.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Comparing word[i..] with the prefix directly for every candidate t is O(n^2 / k) — fine for the small version, too slow here when k is 1.
• If no candidate works the answer is ceil(n / k), reached when t * k >= n.
• z[0] is never consulted (t starts at 1), so its convention does not matter.

Reference solution

Python

def minimumTimeToInitialState(word: str, k: int) -> int:
    n = len(word)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and word[z[i]] == word[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    t = 1
    while t * k < n:
        if z[t * k] == n - t * k:
            return t
        t += 1
    return t

Java

public static int minimumTimeToInitialState(String word, int k) {
    int n = word.length();
    int[] z = new int[n];
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = Math.min(r - i, z[i - l]);
        while (i + z[i] < n && word.charAt(z[i]) == word.charAt(i + z[i])) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    int t = 1;
    while ((long) t * k < n) {
        if (z[t * k] == n - t * k) return t;
        t++;
    }
    return t;
}

C++

int minimumTimeToInitialState(string word, int k) {
    int n = word.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && word[z[i]] == word[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    int t = 1;
    while ((long long) t * k < n) {
        if (z[t * k] == n - t * k) return t;
        t++;
    }
    return t;
}

JavaScript

var minimumTimeToInitialState = function(word, k) {
    var n = word.length;
    var z = new Array(n).fill(0);
    var l = 0, r = 0;
    for (var i = 1; i < n; i++) {
        if (i < r) z[i] = Math.min(r - i, z[i - l]);
        while (i + z[i] < n && word.charCodeAt(z[i]) === word.charCodeAt(i + z[i])) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    var t = 1;
    while (t * k < n) {
        if (z[t * k] === n - t * k) return t;
        t++;
    }
    return t;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard
• Find the Original Typed String II Hard