3137. 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

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

题目限制：

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

题解

本题主要依赖哈希表解题，根据题目描述，循环遍历一次数组，将数组分割为每一段长度为 k 的子数组，利用哈希表保存其出现次数，找到最多的那个，剩下的子数组即为需要操作的子数组，剩下几个就需要几次。

实现代码：

/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var minimumOperationsToMakeKPeriodic = function(word, k) {
    const hash = new Map();
    for (let i = 0; i < word.length; i += k) {
        const str = word.slice(i, i + k);
        hash.set(
            str,
            (hash.get(str) || 0) + 1
        );
    }
    let max = 0;
    for (let [key, val] of hash) {
        max = Math.max(max, val);
    }
    return word.length/k - max;
};

可以在遍历数组是，一起计算 max：

/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var minimumOperationsToMakeKPeriodic = function(word, k) {
    const hash = new Map();
    let max = 0;
    for (let i = 0; i < word.length; i += k) {
        const str = word.slice(i, i + k);
        hash.set(
            str,
            (hash.get(str) || 0) + 1
        );
        max = Math.max(max, hash.get(str));
    }
    return word.length/k - max;
};

因数: 整数a除以整数b(b≠0)的商正好是整数而没有余数时，称b是a的因数。 ↩

题目描述 中等​

题解​

Footnotes​

题目描述中等

题解

Footnotes