3137. Minimum Number of Operations to Make Word K-Periodic LeetCode Solution
In this guide, you will get 3137. Minimum Number of Operations to Make Word K-Periodic LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Operations to Make Word K-Periodic problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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”.
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”.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3137. Minimum Number of Operations to Make Word K-Periodic LeetCode Solution in C++
class Solution {
public:
int minimumOperationsToMakeKPeriodic(string word, int k) {
unordered_map<string, int> count;
int maxFreq = 0;
for (int i = 0; i < word.length(); i += k)
++count[word.substr(i, k)];
for (const auto& [_, freq] : count)
maxFreq = max(maxFreq, freq);
return word.length() / k - maxFreq;
}
}; /* code provided by PROGIEZ */
3137. Minimum Number of Operations to Make Word K-Periodic LeetCode Solution in Java
class Solution {
public int minimumOperationsToMakeKPeriodic(String word, int k) {
Map<String, Integer> count = new HashMap<>();
for (int i = 0; i < word.length(); i += k)
count.merge(word.substring(i, i + k), 1, Integer::sum);
final int maxFreq = count.values().stream().max(Integer::compare).orElse(0);
return word.length() / k - maxFreq;
}
} // code provided by PROGIEZ
3137. Minimum Number of Operations to Make Word K-Periodic LeetCode Solution in Python
class Solution:
def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
count = collections.Counter(word[i:i + k] for i in range(0, len(word), k))
return len(word) // k - max(count.values()) # code by PROGIEZ
