原创

学习之路任重而道远

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" 。

思路

要点1：选择的两个下标要能被k整除，k是word长度的因数，可选择的下标为——0, k, k*2..., word.size() - k

要点2：K周期字符串要以k为周期，即我们每次选择的子串中必有一个会成为最后的循环依据

方法

找到重复次数最多的长度为k的字串数量，将其他不是该字串的更换为该字串即可

代码

class Solution {
public:
    int minimumOperationsToMakeKPeriodic(string word, int k) {
        unordered_map<string, int> hashmap;
        int length = word.size();
        pair<string, int> max_pair(make_pair("", 0));
        for(int i = 0; i < length; i += k)
            if(++hashmap[word.substr(i, k)] > max_pair.second) max_pair=make_pair(word.substr(i, k), hashmap[word.substr(i, k)]);
        return length / k - max_pair.second;
    }
};