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

## Description

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

Example 1:

Input: word = "leetcodeleet", k = 4

Output: 1

Explanation:

We can obtain a 4-periodic string by picking i = 4 and j = 0. After this operation, word becomes equal to "leetleetleet".

Example 2:

Input: word = "leetcoleet", k = 2

Output: 3

Explanation:

We can obtain a 2-periodic string by applying the operations in the table below.

i j word
0 2 etetcoleet
4 0 etetetleet
6 0 etetetetet

Constraints:

• 1 <= n == word.length <= 105
• 1 <= k <= word.length
• k divides word.length.
• word consists only of lowercase English letters.

## Solutions

### Solution 1: Counting

We can divide the string word into substrings of length $k$, then count the occurrence of each substring, and finally return $n/k$ minus the count of the most frequently occurring substring.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string word.

• 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;
}
};

• 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())


• 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;
}