Minimum Number of Operations to Make Word K-Periodic Solution
Minimum Number of Operations to Make Word K-Periodic solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Operations to Make Word K-Periodic is a medium coding problem on strings, hash table and counting, asked in Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string word of length n and an integer k that divides n.
In one operation you pick two indices i and j, both divisible by k, and replace the length-k substring starting at i with the length-k substring starting at j — that is, word[i..i + k - 1] becomes a copy of word[j..j + k - 1].
The word is k-periodic if it equals some length-k string s repeated n / k times (for example, "ababab" is 2-periodic with s = "ab"). Return the minimum number of operations needed to make word k-periodic.
Example 1
Input: word = "codekatacode", k = 4
Output: 1
Explanation: Copy the block at index 0 over `kata`, giving `codecodecode`.
Example 2
Input: word = "leetcoleet", k = 2
Output: 3
Explanation: The blocks are `le`, `et`, `co`, `le`, `et`; keeping `le` (or `et`) needs the other three blocks replaced.
Example 3
Input: word = "aaaa", k = 1
Output: 0
Constraints
1 <= n == word.length <= 10^51 <= k <= word.lengthk divides word.lengthword consists only of lowercase English letters
Hints for Minimum Number of Operations to Make Word K-Periodic
Hint 1
An operation only ever copies a whole aligned block onto another aligned block. Split the word into its
n / kblocks.Hint 2
The final periodic word repeats a single block. Any block that already equals it needs no operation; every other block needs exactly one.
Hint 3
So choose the block value that occurs most often: the answer is
n / k − (highest frequency). Count block frequencies in a hash map.
How to solve Minimum Number of Operations to Make Word K-Periodic
The operations copy existing aligned blocks, so the final word repeats one of the current blocks. Keep the most frequent block and overwrite every block that differs, one operation each.
Approach
- Cut
wordinto the blocksword[i..i + k - 1]fori = 0, k, 2k, …. - Count how many times each block string occurs.
- Return
n / k − maxCount.
Why it works
Each operation changes one block, so a block that differs from the final pattern costs at least one operation, and one is enough (copy a block that already holds the pattern). The final pattern must be some existing block, because copies never create a new block value — so the best pattern is the most frequent block.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Only aligned blocks (starting at multiples of
k) take part; overlapping substrings do not. - Counting characters instead of whole blocks gives the wrong answer —
abandbaare different blocks.
Reference solution
Python
from collections import Counter
def minimumOperationsToMakeKPeriodic(word: str, k: int) -> int:
n = len(word)
counts = Counter(word[i:i + k] for i in range(0, n, k))
return n // k - max(counts.values())Java
public static int minimumOperationsToMakeKPeriodic(String word, int k) {
HashMap<String, Integer> counts = new HashMap<>();
int best = 0;
for (int i = 0; i < word.length(); i += k) {
int c = counts.merge(word.substring(i, i + k), 1, Integer::sum);
best = Math.max(best, c);
}
return word.length() / k - best;
}C++
int minimumOperationsToMakeKPeriodic(string word, int k) {
unordered_map<string, int> counts;
int best = 0;
for (size_t i = 0; i < word.size(); i += k) {
best = max(best, ++counts[word.substr(i, k)]);
}
return (int) word.size() / k - best;
}JavaScript
var minimumOperationsToMakeKPeriodic = function(word, k) {
var counts = new Map();
var best = 0;
for (var i = 0; i < word.length; i += k) {
var block = word.substring(i, i + k);
var c = (counts.get(block) || 0) + 1;
counts.set(block, c);
if (c > best) best = c;
}
return word.length / k - best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets