日期: 2024 年 8 月 17 日

目标

给你一个长度为 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^5
• 1 <= k <= word.length
• k 能整除 word.length 。
• word 仅由小写英文字母组成。

思路

给定字符串 word 以及周期 k（k 为 word 长度的因数，即可以被 word 长度整除），将字符串分为 word.length()/k 份，每次操作可以将其中一份替换为其它份字符串。问最少需要多少次操作，可以使每份字符串都相等。

用份数减去出现次数最多的子串即可。

代码

/**
 * @date 2024-08-17 20:44
 */
public class MinimumOperationsToMakeKPeriodic3137 {

    /**
     * 使用substring效率更高
     * 循环步长为k
     */
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int n = word.length();
        int max = 0;
        int parties = n / k;
        // 优化点：指定初始容量
        Map<String, Integer> map = new HashMap<>(parties);
        // 出错点，这里循环条件使 <= n，而非小于n，因为我们使用的使substring，不包括结束index
        for (int i = k; i <= n; i += k) {
            String period = word.substring(i - k, i);
            // 优化点：这里可以直接拿到cnt，不用后面再从map里get
            int cnt = map.merge(period, 1, Integer::sum);
            max = Math.max(cnt, max);
        }
        return parties - max;
    }

}

性能