Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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 summary: 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".
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"leetcodeleet" 4
"leetcoleet" 2
maximum-repeating-substring)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3137: Minimum Number of Operations to Make Word K-Periodic
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;
}
}
// Accepted solution for LeetCode #3137: Minimum Number of Operations to Make Word K-Periodic
func minimumOperationsToMakeKPeriodic(word string, k int) int {
cnt := map[string]int{}
n := len(word)
mx := 0
for i := 0; i < n; i += k {
s := word[i : i+k]
cnt[s]++
mx = max(mx, cnt[s])
}
return n/k - mx
}
# Accepted solution for LeetCode #3137: Minimum Number of Operations to Make Word K-Periodic
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())
// Accepted solution for LeetCode #3137: Minimum Number of Operations to Make Word K-Periodic
/**
* [3137] Minimum Number of Operations to Make Word K-Periodic
*/
pub struct Solution {}
// submission codes start here
use std::collections::HashMap;
impl Solution {
pub fn minimum_operations_to_make_k_periodic(word: String, k: i32) -> i32 {
let mut map = HashMap::new();
let mut result = i32::MAX;
let n = word.len();
let k = k as usize;
for i in (0..n).step_by(k) {
let key = &word[i..i + k];
let entry = map.entry(key).or_insert(0);
*entry += 1;
result = result.min((n / k) as i32 - *entry);
}
result
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_3137() {
assert_eq!(
1,
Solution::minimum_operations_to_make_k_periodic("leetcodeleet".to_owned(), 4)
);
}
}
// Accepted solution for LeetCode #3137: Minimum Number of Operations to Make Word K-Periodic
function minimumOperationsToMakeKPeriodic(word: string, k: number): number {
const cnt: Map<string, number> = new Map();
const n: number = word.length;
let mx: number = 0;
for (let i = 0; i < n; i += k) {
const s = word.slice(i, i + k);
cnt.set(s, (cnt.get(s) || 0) + 1);
mx = Math.max(mx, cnt.get(s)!);
}
return Math.floor(n / k) - mx;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.