Minimum Time to Revert Word to Initial State II

Problem Description

Given a 0-indexed string word of length n and an integer k, you are allowed to perform the following operation every second:

1. Remove the first k characters of word.
2. Append any k characters to the end of word. Both parts of the operation must be done every second. Find the minimum number of seconds (greater than zero) required such that, by choosing the appended characters appropriately at each step, word becomes equal to its original state.

Key Insights

• At each operation the first k characters are removed and the appended k characters can be chosen arbitrarily.
• In effect, part of the word is “inherited” from the previous state (the substring from index k to n – 1) while the last k characters can be “fixed” by our choice.
• With a proper strategy, we “rebuild” the original word from right to left. That is, in the final state the block that came from the previous operations must coincide with the corresponding prefix of the original word.
• If after t operations the inherited part (of length n – tk, when tk < n) already matches the corresponding prefix of the original word, then we can “fill” the rest arbitrarily (by choosing exact characters from S) to restore the full string.
• When t*k ≥ n, the entire word is determined by our appended choices so the initial word can be re‐established trivially.
• Thus the answer is the minimum t ≥ 1 such that either tk ≥ n or, if tk < n, the substring word[tk : n] equals word[0 : n – tk].

Space and Time Complexity

Time Complexity: O(n) overall.
Space Complexity: O(n) for storing the hash arrays (or prefix table) when using a rolling hash.

Solution

The idea is to “simulate” the operations mathematically rather than performing each string operation. After t operations, the leftmost n – tk characters of the new word come from shifting the original word t times; they are fixed and cannot be changed by later choices. In order to reassemble the original word S, when tk < n the following must hold:   S[tk : n] = S[0 : n – tk]. If this condition does not hold for any t with tk < n, then we must choose t so that tk ≥ n (in which case every character is appended in the last step, letting us pick S exactly).
Since directly checking equality for every candidate t in O(n) time per candidate would be too slow when k = 1, we use a rolling hash (or similar string matching technique) to compare the required substrings in O(1) time per candidate. The algorithm is:

1. Precompute a rolling hash for the string S.
2. Iterate t from 1 upward. For each t:  a. If tk ≥ n, return t.  b. Otherwise, check if the hash of S[tk : n] equals the hash of S[0 : n – t*k]. If yes, return t. This yields the minimum t (seconds) required.

Code Solutions