3137. Minimum Number of Operations to Make Word K-Periodic

You are given a string word of size n, and an integer k such that k divides n.

In one operation, you can pick any two indices i and j, that are divisible by k, then replace the substring of length k starting at i with the substring of length k starting at j. That is, replace the substring word[i..i + k - 1] with the substring word[j..j + k - 1].

Return the minimum number of operations required to make word k-periodic.

We say that word is k-periodic if there is some string s of length k such that word can be obtained by concatenating s an arbitrary number of times. For example, if word == “ababab”, then word is 2-periodic for s = "ab".

class Solution {
public:
    int minimumOperationsToMakeKPeriodic(string word, int k) {
        unordered_map<string,int> freq;
        int res = INT_MAX, d = word.length() / k;
        for(int i = 0; i < word.length(); i += k) {
            string s = "";
            for(int j = 0; j < k; j++) {
                s.push_back(word[j+i]);
            }
            ++freq[s];
            res = min(res, d - freq[s]);
        }
        return res;
    }
};