Minimum Number of Operations to Make Word K-Periodic
MedPrompt
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.lengthkdividesword.length.wordconsists only of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves first extracting all the k-length substrings and then using a brute-force method with nested loops to find the frequency of each substring. The goal is to identify the substring that appears most often, which will be the target for making the word k-periodic.
Algorithm
- Calculate the total number of k-length substrings,
m = n / k. - Create a list to store all these
msubstrings. - Iterate from
i = 0ton-1with a step ofk. In each step, extractword.substring(i, i + k)and add it to the list. - Initialize
maxFrequency = 0. - Iterate through the list of substrings with an outer loop (let's say index
i). - Inside the outer loop, initialize
currentFrequency = 0. - Start an inner loop (index
j) to compare the substring at indexiwith all other substrings in the list. - If
substrings.get(i)is equal tosubstrings.get(j), incrementcurrentFrequency. - After the inner loop finishes, update
maxFrequency = Math.max(maxFrequency, currentFrequency). - After the outer loop finishes, the result is
m - maxFrequency.
Walkthrough
The algorithm starts by dividing the input string word into n/k non-overlapping substrings, each of length k. These substrings are stored in a list. Then, it iterates through this list of substrings. For each substring, it performs another iteration through the entire list to count how many times it appears. A variable maxFrequency keeps track of the highest frequency found so far. After checking each substring, maxFrequency is updated if the current substring's frequency is higher. Once the most frequent substring and its count (maxFrequency) are determined, the minimum number of operations can be calculated. The total number of substrings is n/k. To make the word k-periodic, we want to make all substrings identical to the most frequent one. The number of substrings that already match is maxFrequency. Therefore, the number of substrings that need to be changed (which corresponds to the number of operations) is (n/k) - maxFrequency.
import java.util.ArrayList;import java.util.List; class Solution { public int minimumOperationsToMakeKPeriodic(String word, int k) { int n = word.length(); int numSubstrings = n / k; if (numSubstrings <= 1) { return 0; } List<String> substrings = new ArrayList<>(); for (int i = 0; i < n; i += k) { substrings.add(word.substring(i, i + k)); } int maxFrequency = 0; for (int i = 0; i < numSubstrings; i++) { int currentFrequency = 0; for (int j = 0; j < numSubstrings; j++) { if (substrings.get(i).equals(substrings.get(j))) { currentFrequency++; } } maxFrequency = Math.max(maxFrequency, currentFrequency); } return numSubstrings - maxFrequency; }}Complexity
Time
O(n^2 / k). Let `m = n/k` be the number of substrings. Extracting all substrings takes `m * k = O(n)` time. The nested loops run `m * m` times. Inside the inner loop, string comparison takes `O(k)` time. So, the counting part is `O(m^2 * k) = O((n/k)^2 * k) = O(n^2 / k)`. The total time is dominated by the counting part.
Space
O(n). We store `m = n/k` substrings, each of length `k`. The total space required for the list is `m * k = O(n)`.
Trade-offs
Pros
Simple to understand and implement.
It doesn't require complex data structures.
Cons
Inefficient for large inputs due to the quadratic time complexity relative to the number of substrings.
Can lead to 'Time Limit Exceeded' on platforms with large test cases.
An intermediate approach between brute-force and a hash map involves sorting the substrings. By sorting, all identical substrings become adjacent, making it easy to count the frequency of the most common one in a single pass.
Algorithm
- Calculate the total number of k-length substrings,
m = n / k. - Create a list and populate it with all
msubstrings from theword. - Sort the list of substrings.
- Initialize
maxFrequency = 1andcurrentFrequency = 1(assumingm > 0). - Iterate through the sorted list from the second element (
i = 1). - Compare the current substring
substrings.get(i)with the previous onesubstrings.get(i-1). - If they are the same, increment
currentFrequency. - If they are different, reset
currentFrequencyto 1. - In each step, update
maxFrequency = Math.max(maxFrequency, currentFrequency). - After the loop, the result is
m - maxFrequency.
Walkthrough
Similar to the brute-force approach, this method begins by extracting all n/k k-length substrings into a list. The key difference is that instead of using nested loops, we sort this list of substrings lexicographically. After sorting, all occurrences of the same substring will be grouped together. We can then iterate through the sorted list once to find the longest contiguous block of identical substrings. The length of this block is the maxFrequency. For example, if the substrings are ["c", "a", "c", "b", "c"], after sorting they become ["a", "b", "c", "c", "c"]. A single pass can find that "c" appears 3 times, which is the maximum frequency. Finally, the result is calculated as (n/k) - maxFrequency.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int minimumOperationsToMakeKPeriodic(String word, int k) { int n = word.length(); int numSubstrings = n / k; if (numSubstrings <= 1) { return 0; } List<String> substrings = new ArrayList<>(); for (int i = 0; i < n; i += k) { substrings.add(word.substring(i, i + k)); } Collections.sort(substrings); int maxFrequency = 1; int currentFrequency = 1; for (int i = 1; i < numSubstrings; i++) { if (substrings.get(i).equals(substrings.get(i - 1))) { currentFrequency++; } else { currentFrequency = 1; } maxFrequency = Math.max(maxFrequency, currentFrequency); } return numSubstrings - maxFrequency; }}Complexity
Time
O(n * log(n/k)). Let `m = n/k`. Extracting substrings takes `O(n)`. Sorting a list of `m` strings, where each comparison takes `O(k)`, results in a time complexity of `O(m * log(m) * k)`. This simplifies to `O((n/k) * log(n/k) * k) = O(n * log(n/k))`. The final pass to count frequencies takes `O(m * k) = O(n)`. The sorting step dominates.
Space
O(n). We need to store `m = n/k` substrings of length `k`, which amounts to `m * k = O(n)` space.
Trade-offs
Pros
More efficient than the brute-force approach.
Conceptually simple, relying on a standard sorting algorithm.
Cons
Slower than the hash map approach.
Requires
O(n)auxiliary space, similar to the other approaches.
The most efficient approach is to use a hash map (or a dictionary) to count the frequencies of each unique k-length substring. This avoids both nested loops and sorting, reducing the time complexity to linear.
Algorithm
- Initialize a hash map,
Map<String, Integer> frequencyMap, to store the frequency of each substring. - Initialize
maxFrequency = 0. - Calculate the total number of substrings,
m = n / k. - Iterate from
i = 0ton-1with a step ofk. - In each step, extract the substring
s = word.substring(i, i + k). - Update the frequency of
sin thefrequencyMap.frequencyMap.put(s, frequencyMap.getOrDefault(s, 0) + 1). - After updating, get the new frequency of
sand updatemaxFrequency = Math.max(maxFrequency, newFrequency). - After the loop, the result is
m - maxFrequency.
Walkthrough
The core idea is to find the most frequent k-length substring and make all other substrings identical to it. The number of operations will be the total number of substrings minus the frequency of the most common one. The algorithm iterates through the word in steps of k, extracting each k-length substring. For each extracted substring, it uses a hash map to store and update its frequency count. The substring itself is the key, and its frequency is the value. While populating the hash map, we can also keep track of the maximum frequency seen so far. This avoids a separate pass through the map's values later. After iterating through all substrings, we will have the count of the most frequent one (maxFrequency). The total number of substrings is n/k. The minimum number of operations is then (n/k) - maxFrequency. This is because we keep the maxFrequency substrings that are already the desired pattern and change the rest.
import java.util.HashMap;import java.util.Map; class Solution { public int minimumOperationsToMakeKPeriodic(String word, int k) { int n = word.length(); Map<String, Integer> frequencyMap = new HashMap<>(); int maxFrequency = 0; for (int i = 0; i < n; i += k) { String sub = word.substring(i, i + k); int currentFrequency = frequencyMap.getOrDefault(sub, 0) + 1; frequencyMap.put(sub, currentFrequency); maxFrequency = Math.max(maxFrequency, currentFrequency); } int numSubstrings = n / k; return numSubstrings - maxFrequency; }}Complexity
Time
O(n). Let `m = n/k` be the number of substrings. The loop runs `m` times. Inside the loop, `substring()` takes `O(k)` time, and hash map operations (get, put) take an average of `O(k)` time (due to key hashing and comparison). The total time is `m * O(k) = (n/k) * O(k) = O(n)`.
Space
O(n). In the worst-case scenario, all `m = n/k` substrings are unique. Storing them in the hash map requires space proportional to the total length of all unique substrings, which is at most `m * k = O(n)`.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution for the given constraints.
Cons
Uses extra space for the hash map, which can be significant if the number of unique substrings is large.
Solutions
Solution
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())Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.