2024-12-14：K 周期字符串需要的最少操作次数。用 go 语言，给定一个长度为 n 的字符串 word 和一个整数 k，k 是 n 的因数。每次操作可以选择两个下标 i 和 j，使得 i 和 j 都可以被 k 整除，然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。要使得 word 成为一个 K 周期字符串，需要进行最少的操作次数。

一个 K 周期字符串是指存在一个长度为 k 的字符串 s，通过多次连接 s 可以得到 word。比如，如果 word == "ababab"，那么当 s = "ab"时，word 是一个 2 周期字符串。

现在，请计算使 word 成为 K 周期字符串所需的最少操作次数。

1 <= n == word.length <= 100000。

1 <= k <= word.length。

k 能整除 word.length 。

word 仅由小写英文字母组成。

输入：word = "leetcodeleet", k = 4。

输出：1。

解释：可以选择 i = 4 和 j = 0 获得一个 4 周期字符串。这次操作后，word 变为 "leetleetleet"。

答案 2024-12-14：

chatgpt

题目来自 leetcode3137。

大体步骤如下：

1.初始化变量 n 为字符串 word 的长度，并设定变量 res 初始值为最大整数。

2.创建一个空的计数映射 count，用于存储不同子串的出现次数。

3.遍历字符串 word 中长度为 k 的子串，依次检查每个子串。

4.在循环中，统计每个长度为 k 的子串出现的次数，更新 res 为使得 word 成为 K 周期字符串所需的最少操作次数。

5.返回最少操作次数 res。

总体时间复杂度：

• 遍历整个字符串 word 需要 O(n/k) 的时间。

• 在每一步中，计算和更新 res 的时间复杂度为 O(1)。

• 因此，总体时间复杂度为 O(n/k)。

总体额外空间复杂度：

• 需要额外的空间来存储计数映射 count，其大小取决于字符串中包含 unique 子串的数量，最坏情况下可达到 O(n/k)。

• 因此，总体额外空间复杂度为 O(n/k)。

Go 完整代码如下：

package main
import (  "fmt"  "math")
func minimumOperationsToMakeKPeriodic(word string, k int) int {  n, res := len(word), math.MaxInt  count := map[string]int{}  for i := 0; i < n; i += k {    count[word[i:i+k]]++    res = min(res, n/k-count[word[i:i+k]])  }  return res}
func main() {  word := "leetcodeleet"  k := 4  fmt.Println(minimumOperationsToMakeKPeriodic(word, k))}

Rust 完整代码如下：

use std::collections::HashMap;
fn min_operations_to_make_k_periodic(word: &str, k: usize) -> i32 {    let n = word.len();    let mut res = i32::MAX;    let mut count: HashMap<&str, i32> = HashMap::new();
    for i in (0..n).step_by(k) {        let sub_str = &word[i..i+k];        *count.entry(sub_str).or_insert(0) += 1;        res = res.min((n / k) as i32 - *count.get(&sub_str).unwrap_or(&0));    }
    res}
fn main() {    let word = "leetcodeleet";    let k = 4;    println!("{}", min_operations_to_make_k_periodic(word, k));}