Medium

题目描述

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

在一次操作中，你可以选择任意两个下标 i 和 j，且它们都能被 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 周期字符串。

提示：

  • 1 <= n == word.length <= 10^5
  • 1 <= k <= word.length
  • k 整除 word.length
  • word 只包含小写英文字母

解题思路

这道题的核心思路是贪心算法：要使字符串变为 k 周期字符串，最终所有位置 0, k, 2k, ... 上的长度为 k 的子字符串都必须相同。

解题思路：

  1. 分割子字符串：将字符串按照 k 的长度分割，得到 n/k 个子字符串，这些子字符串的起始位置分别是 0, k, 2k, ...

  2. 统计频率：使用哈希表统计每个长度为 k 的子字符串出现的次数

  3. 选择最优目标：找出出现次数最多的子字符串作为最终的周期模式，这样可以最大化保留已有的子字符串，最小化需要替换的次数

  4. 计算操作次数：总的子字符串数量减去最频繁子字符串的出现次数，就是需要的最少操作次数

例如对于 "leetcodeleet" 和 k=4：

  • 分割得到：["leet", "code", "leet"]
  • 统计频率："leet" 出现 2 次，"code" 出现 1 次
  • 选择 "leet" 作为目标模式
  • 需要操作次数：3 - 2 = 1

代码实现

class Solution {
public:
    int minimumOperationsToMakeKPeriodic(string word, int k) {
        unordered_map<string, int> count;
        int n = word.length();
        
        // 统计每个长度为k的子字符串的出现次数
        for (int i = 0; i < n; i += k) {
            string substr = word.substr(i, k);
            count[substr]++;
        }
        
        // 找出出现次数最多的子字符串
        int maxCount = 0;
        for (auto& p : count) {
            maxCount = max(maxCount, p.second);
        }
        
        // 总数减去最大频率就是需要的操作次数
        return n / k - maxCount;
    }
};

class Solution:
    def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
        from collections import Counter
        
        # 提取所有长度为k的子字符串
        substrings = []
        for i in range(0, len(word), k):
            substrings.append(word[i:i+k])
        
        # 统计频率
        count = Counter(substrings)
        
        # 找出最大频率
        max_count = max(count.values())
        
        # 总数减去最大频率就是需要的操作次数
        return len(substrings) - max_count

public class Solution {
    public int MinimumOperationsToMakeKPeriodic(string word, int k) {
        var count = new Dictionary<string, int>();
        int n = word.Length;
        
        // 统计每个长度为k的子字符串的出现次数
        for (int i = 0; i < n; i += k) {
            string substr = word.Substring(i, k);
            if (count.ContainsKey(substr)) {
                count[substr]++;
            } else {
                count[substr] = 1;
            }
        }
        
        // 找出出现次数最多的子字符串
        int maxCount = 0;
        foreach (var pair in count) {
            maxCount = Math.Max(maxCount, pair.Value);
        }
        
        // 总数减去最大频率就是需要的操作次数
        return n / k - maxCount;
    }
}

var minimumOperationsToMakeKPeriodic = function(word, k) {
    const count = new Map();
    const n = word.length;
    
    // 统计每个长度为k的子字符串的出现次数
    for (let i = 0; i < n; i += k) {
        const substr = word.substring(i, i + k);
        count.set(substr, (count.get(substr) || 0) + 1);
    }
    
    // 找出出现次数最多的子字符串
    let maxCount = 0;
    for (const freq of count.values()) {
        maxCount = Math.max(maxCount, freq);
    }
    
    // 总数减去最大频率就是需要的操作次数
    return Math.floor(n / k) - maxCount;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个字符串一次，每次提取长度为k的子字符串
空间复杂度O(n)最坏情况下所有子字符串都不同，哈希表需要存储n/k个不同的字符串

相关题目