LeetCode 3137 - Minimum Number of Operations to Make Word K-Periodic
The problem asks us to transform a given string word of length n into a k-periodic string using the minimum number of operations. A string is k-periodic if it can be formed by repeating a substring s of length k multiple times.
Difficulty: 🟡 Medium
Topics: Hash Table, String, Counting
Solution
Problem Understanding
The problem asks us to transform a given string word of length n into a k-periodic string using the minimum number of operations. A string is k-periodic if it can be formed by repeating a substring s of length k multiple times. Each operation allows us to pick two substrings of length k that start at indices divisible by k and replace the first substring with the second. The goal is to determine the minimum number of such operations to make the entire string k-periodic.
The input consists of a string word and an integer k that divides the length of the string. The output is an integer representing the minimum number of operations required. The constraints tell us the string can be up to 100,000 characters, so any algorithm with complexity higher than O(n) or O(n log n) may be too slow.
Important edge cases include when k = n (the string is already trivially k-periodic), when all characters are identical (0 operations needed), and when no substrings match initially (requiring maximum operations). The guarantee that k divides n simplifies indexing and ensures no partial blocks exist.
Approaches
A brute-force approach would attempt to try every possible substring replacement to see if the string becomes k-periodic. This would involve iterating over all combinations of substrings of length k and recursively applying operations until k-periodicity is achieved. While correct, this approach is far too slow for large n because the number of combinations grows exponentially.
The key observation for an optimal solution is that the problem can be broken down position-wise modulo k. Specifically, each character at position i contributes to the periodic pattern at position i % k. Therefore, to minimize operations, we can focus on each of the k positions across all repeated blocks, count the frequency of each character at that position, and replace all other characters with the most frequent one. The sum of replacements across all positions gives the minimum operations.
This is a counting and frequency problem across modular positions.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O((n/k)!) | O(n) | Try all substring swaps; exponential in number of blocks |
| Optimal | O(n) | O(k*26) ≈ O(k) | Count frequencies of characters at each modulo k position; replace all but the most frequent |
Algorithm Walkthrough
- Initialize an array of dictionaries
freqof sizek. Each dictionary will store character frequencies for a given modulo k position. - Iterate over each character in the string using its index
i. - For each character
cat indexi, increment the frequency count infreq[i % k][c]. - After building all frequency counts, initialize a variable
operationsto 0. - For each position
0 <= pos < k, compute the number of replacements as the total characters at this position minus the maximum frequency for that position. - Sum these replacements across all positions to obtain the total minimum operations.
- Return the total operations.
Why it works: By making every character at a given modulo k position equal to the most frequent character in that position, we ensure that all repeated blocks will match exactly in all positions, forming a k-periodic string. This guarantees the minimum number of operations because any other choice would require more replacements.
Python Solution
class Solution:
def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
n = len(word)
freq = [{} for _ in range(k)]
for i, c in enumerate(word):
mod_pos = i % k
freq[mod_pos][c] = freq[mod_pos].get(c, 0) + 1
operations = 0
for pos in range(k):
total_chars = sum(freq[pos].values())
max_freq = max(freq[pos].values())
operations += total_chars - max_freq
return operations
The implementation first counts character frequencies at each modulo k position. Then, for each position, it computes how many characters need to be replaced to make all characters at that position equal to the most frequent one. The sum of these replacements gives the minimum number of operations.
Go Solution
func minimumOperationsToMakeKPeriodic(word string, k int) int {
n := len(word)
freq := make([]map[byte]int, k)
for i := 0; i < k; i++ {
freq[i] = make(map[byte]int)
}
for i := 0; i < n; i++ {
modPos := i % k
freq[modPos][word[i]]++
}
operations := 0
for i := 0; i < k; i++ {
maxFreq := 0
total := 0
for _, count := range freq[i] {
total += count
if count > maxFreq {
maxFreq = count
}
}
operations += total - maxFreq
}
return operations
}
The Go solution mirrors the Python logic. It uses a slice of maps to count frequencies at each modulo k position. Differences include explicit map initialization for each position and iteration over map values instead of dictionary methods.
Worked Examples
Example 1: word = "leetcodeleet", k = 4
Positions modulo 4:
| Index % 4 | Characters | Frequencies | Max Freq | Replacements |
|---|---|---|---|---|
| 0 | l, l, l | l:3 | 3 | 0 |
| 1 | e, e, e | e:3 | 3 | 0 |
| 2 | e, t, e | e:2, t:1 | 2 | 1 |
| 3 | t, c, t | t:2, c:1 | 2 | 1 |
Total operations = 0 + 0 + 1 + 0 = 1
Example 2: word = "leetcoleet", k = 2
Positions modulo 2:
| Index % 2 | Characters | Frequencies | Max Freq | Replacements |
|---|---|---|---|---|
| 0 | l, e, c, l, e | l:2, e:2, c:1 | 2 | 3 |
| 1 | e, t, o, e, t | e:2, t:2, o:1 | 2 | 3 |
Total operations = 3
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We iterate through the string once to build frequency counts and then O(k) to compute replacements, which is bounded by n |
| Space | O(k*26) ≈ O(k) | We maintain frequency dictionaries/maps for each of the k positions, each storing at most 26 letters |
The complexity is efficient for the input constraints, allowing up to 100,000 characters without performance issues.
Test Cases
# Provided examples
assert Solution().minimumOperationsToMakeKPeriodic("leetcodeleet", 4) == 1 # Example 1
assert Solution().minimumOperationsToMakeKPeriodic("leetcoleet", 2) == 3 # Example 2
# Edge cases
assert Solution().minimumOperationsToMakeKPeriodic("aaaaa", 1) == 0 # all same
assert Solution().minimumOperationsToMakeKPeriodic("abcabcabc", 3) == 0 # already k-periodic
assert Solution().minimumOperationsToMakeKPeriodic("abcdef", 2) == 3 # all different
assert Solution().minimumOperationsToMakeKPeriodic("abacabadabacaba", 7) == 2 # mixed
assert Solution().minimumOperationsToMakeKPeriodic("z"*100000, 1) == 0 # large input, all same
| Test | Why |
|---|---|
| "leetcodeleet", 4 | Validates simple replacement |
| "leetcoleet", 2 | Checks multiple replacements |
| "aaaaa", 1 | Already k-periodic with single character |
| "abcabcabc", 3 | Already k-periodic, no operations |
| "abcdef", 2 | Worst case with all different characters |
| "abacabadabacaba", 7 | Mixed characters, non-trivial minimal operations |
| "z"*100000, 1 | Large input stress test |
Edge Cases
One important edge case is when k = n. In this case, the entire string is considered a single block. The algorithm correctly identifies that no operation is needed because each modulo k position contains exactly one character.
Another edge case occurs when all characters are the same. Here, each modulo position already has a frequency of 100% for one character, so the algorithm correctly returns 0 operations.
A third edge case involves alternating characters with k = 1 or k = 2, which could cause naive solutions to miscount replacements. The modulo-based frequency counting ensures that only necessary replacements are counted, even for repeated patterns across blocks.
This solution generalizes to all such scenarios, correctly computing the minimum number of operations while respecting the constraints.