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

来源第 396 场周赛 Q2难度中等分数1491

题目描述

给你一个长度为 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 仅由小写英文字母组成。

解法

方法一：计数

思考

每次把长 \(k\) 的一块换成另一块，目标是整串由同一块重复而成。枚举目标块再计算替换次数与块数成正比。

操作次数等于块数减去保留次数最多的那种块。统计各块出现次数即可，不必真的改写字符串。

按步长 \(k\) 切片后用计数器取最大值，返回 \(n/k\) 减去该最大值。

我们可以将字符串 word 按照长度为 \(k\) 的子串进行分组，然后统计每个子串出现的次数，最后返回 \(n/k\) 减去出现次数最多的子串的次数即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为字符串 word 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
        n = len(word)
        return n // k - max(Counter(word[i : i + k] for i in range(0, n, k)).values())

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

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

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

function minimumOperationsToMakeKPeriodic(word: string, k: number): number {
    const cnt: Map<string, number> = new Map();
    const n: number = word.length;
    let mx: number = 0;
    for (let i = 0; i < n; i += k) {
        const s = word.slice(i, i + k);
        cnt.set(s, (cnt.get(s) || 0) + 1);
        mx = Math.max(mx, cnt.get(s)!);
    }
    return Math.floor(n / k) - mx;
}

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

题目描述

解法

方法一：计数

评论