Minimum number of operations to make word k periodic

Hash Table String Counting

60.7% acceptance

Feb 24, 2026

123

You are given a string word of size n, and an integer k such that k divides n. In one operation, you can pick any two indices i and j, that are divisible by k, then replace the substring of length k starting at i with the substring of length k starting at j. Return the minimum number of operations required to make word k-periodic. We say that word is k-periodic if there is some string s of length k such that word can be obtained by concatenating s an arbitrary number of times.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_operations_to_make_k_periodic(word: String, k: i32) -> i32 {
    let k = k as usize;
    let n = word.len();
    let blocks = n / k;
    let mut freq: std::collections::HashMap<&str, i32> = std::collections::HashMap::new();
    for i in 0..blocks {
      let chunk = &word[i * k..(i + 1) * k];
      *freq.entry(chunk).or_insert(0) += 1;
    }
    let max_count = freq.values().copied().max().unwrap_or(0);
    (blocks as i32) - max_count
  }
}