K 周期字符串需要的最少操作次数

100275. K 周期字符串需要的最少操作次数

给你一个长度为 n 的字符串 word 和一个整数 k ，其中 k 是 n 的因数。

在一次操作中，你可以选择任意两个下标 i 和 j，其中 0 <= i, j < n ，且这两个下标都可以被 k 整除，然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。也就是说，将子串 word[i..i + k - 1] 替换为子串 word[j..j + k - 1] 。

返回使 word 成为 K 周期字符串 所需的最少操作次数。

如果存在某个长度为 k 的字符串 s，使得 word 可以表示为任意次数连接 s ，则称字符串 word 是 K 周期字符串 。例如，如果 word == "ababab"，那么 word 就是 s = "ab" 时的 2 周期字符串。

示例 1：

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

输出：1

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

示例 2：

输入：word = "leetcoleet", k = 2

输出：3

解释：可以执行以下操作获得一个 2 周期字符串。

i	j	word
0	2	etetcoleet
4	0	etetetleet
6	0	etetetetet

提示：

1 <= n == word.length <= 10⁵
1 <= k <= word.length
k 能整除 word.length 。
word 仅由小写英文字母组成。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minimumOperationsToMakeKPeriodic(string word, int k) { } };

javascript 解法, 执行用时: 79 ms, 内存消耗: 58.9 MB, 提交时间: 2024-08-17 10:11:42

/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var minimumOperationsToMakeKPeriodic = function(word, k) {
    const n = word.length;
    const cnt = new Map();
    for (let i = k; i <= n; i += k) {
        const sub = word.slice(i - k, i);
        cnt.set(sub, (cnt.get(sub) ?? 0) + 1);
    }
    const mx = Math.max(...Array.from(cnt.values()));
    return Math.floor(n / k) - mx;
};

rust 解法, 执行用时: 22 ms, 内存消耗: 3.5 MB, 提交时间: 2024-08-17 10:11:27

use std::collections::HashMap;

impl Solution {
    pub fn minimum_operations_to_make_k_periodic(word: String, k: i32) -> i32 {
        let n = word.len();
        let k = k as usize;
        let mut cnt = HashMap::new();
        for i in (k..=n).step_by(k) {
            *cnt.entry(&word[i - k..i]).or_insert(0) += 1;
        }
        let mx = *cnt.values().max().unwrap();
        (n / k) as i32 - mx
    }
}

golang 解法, 执行用时: 29 ms, 内存消耗: 6.9 MB, 提交时间: 2024-05-06 10:08:57

func minimumOperationsToMakeKPeriodic(word string, k int) int {
	n := len(word)
	cnt := map[string]int{}
	for i := k; i <= n; i += k {
		cnt[word[i-k:i]]++
	}
	mx := 0
	for _, c := range cnt {
		mx = max(mx, c)
	}
	return n/k - mx
}

cpp 解法, 执行用时: 80 ms, 内存消耗: 27.6 MB, 提交时间: 2024-05-06 10:08:33

class Solution {
public:
    int minimumOperationsToMakeKPeriodic(string word, int k) {
        int n = word.size(), mx = 0;
        unordered_map<string, int> cnt;
        for (int i = k; i <= n; i += k) {
            mx = max(mx, ++cnt[word.substr(i - k, k)]);
        }
        return n / k - mx;
    }
};

java 解法, 执行用时: 27 ms, 内存消耗: 44.5 MB, 提交时间: 2024-05-06 10:08:20

class Solution {
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int n = word.length();
        int mx = 0;
        HashMap<String, Integer> cnt = new HashMap<>();
        for (int i = k; i <= n; i += k) {
            String sub = word.substring(i - k, i);
            int c = cnt.merge(sub, 1, Integer::sum); // c = ++cnt[sub]
            mx = Math.max(mx, c);
        }
        return n / k - mx;
    }
}

python3 解法, 执行用时: 102 ms, 内存消耗: 18.4 MB, 提交时间: 2024-05-06 10:08:06

# 统计子串个数
'''
根据题意，我们只能选择首字母下标为 0,k,2k,3k,⋯,n−k 的长为 k 的子串来操作（替换）。
并且，k 周期字符串意味着，所有首字母下标为 0,k,2k,3k,⋯,n−k 的长为 k 的子串均相等。
为使操作次数尽量少，我们可以计算最多保留多少个子串不变。
也就是统计 word 中的这些首字母下标为 0,k,2k,3k,⋯,n−k 的长为 k 的子串中，
出现次数最多的子串的出现次数 mx。用出现次数最多的子串，替换其余子串。
所以用子串的个数 n/k 减去 mx，就是最少操作次数。
'''
class Solution:
    def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
        n = len(word)
        cnt = Counter(word[i - k: i] for i in range(k, n + 1, k))
        mx = max(cnt.values())
        return n // k - mx

上一题

下一题

详情