Watch 8 video solutions for Minimum Number of Operations to Make Word K-Periodic, a medium level problem involving Hash Table, String, Counting. This walkthrough by Aryan Mittal has 1,309 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= k <= word.lengthk divides word.length.word consists only of lowercase English letters.Problem Overview: You are given a string word and an integer k. A string is k-periodic if it can be formed by repeating the same substring of length k. One operation lets you replace any substring of length k with another substring. The task is to compute the minimum number of operations required to make the entire string k-periodic.
Approach 1: Character Frequency Counting (Hash Map) (Time: O(n), Space: O(n))
Split the string into blocks of size k. If the string length is n, you get n / k blocks. For the string to be k-periodic, every block must be identical. Count how many times each k-length substring appears using a hash table from the Hash Table toolkit. The block with the highest frequency should be the final repeating pattern because converting other blocks to it minimizes operations. If the most frequent block appears maxFreq times and there are totalBlocks, the minimum operations equal totalBlocks - maxFreq. This works because each non-matching block must be replaced once. The approach relies on efficient substring extraction and constant-time hash lookups.
Approach 2: Sliding Window Transform Technique (Time: O(n), Space: O(n))
Instead of explicitly slicing blocks first, scan the string using a window of size k and move it in steps of k. Each window represents one periodic segment. Maintain a frequency map of these segments as they appear. This technique avoids creating an intermediate array of blocks and processes segments directly while iterating. After scanning the string, compute the most frequent segment using the frequency map. Just like the previous method, the number of operations required is the number of segments that differ from this dominant pattern. Internally this still depends on substring hashing and counting, tying closely to the Counting pattern used in many string grouping problems.
Recommended for interviews: The hash map frequency approach is what most interviewers expect. It shows that you recognized the core insight: only entire k-length segments matter, and the optimal strategy is aligning all segments to the most common one. A brute-force comparison of all segments demonstrates the initial reasoning, but the hash counting solution proves you can reduce the problem to frequency analysis in linear time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency Counting (Hash Map) | O(n) | O(n) | General case. Clean and intuitive solution using substring frequency. |
| Sliding Window Transform Technique | O(n) | O(n) | Useful when processing segments directly during iteration without building a block array. |