Minimum time to revert word to initial state ii

String Rolling Hash String Matching Hash Function

35.1% acceptance

Feb 25, 2026

159

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. Return the minimum time greater than zero required for word to revert to its initial state.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time_to_initial_state(word: String, k: i32) -> i32 {
    let n = word.len();
    let k = k as usize;
    let w = word.as_bytes();
    // Build Z-array in O(n): z[i] = length of longest substring starting at i
    // that equals a prefix of w. So z[skip] >= n-skip means w[skip..] == w[..n-skip].
    let mut z = vec![0usize; n];
    z[0] = n;
    let (mut l, mut r) = (0usize, 0usize);
    for i in 1..n {
      if i < r {
        z[i] = (r - i).min(z[i - l]);
      }
      while i + z[i] < n && w[z[i]] == w[i + z[i]] {
        z[i] += 1;
      }
      if i + z[i] > r {
        l = i;
        r = i + z[i];
      }
    }
    for t in 1usize.. {
      let skip = t * k;
      if skip >= n { return t as i32; }
      if z[skip] >= n - skip { return t as i32; }
    }
    unreachable!()
  }
}