Minimum Number of Operations to Make Word K-Periodic solution and explanation
Google
6 more videos on this problem
3137. Minimum Number of Operations to Make Word K-Periodic | Hash MapAryan Mittal · 7:47 · 1K views
3137 Minimum Number of Operations to Make Word K Periodic || Frequency Count 🔥 || Map + Substring ✅Ayush Rao · 6:11 · 455 views
B.LEETCODE Minimum Number of Operations to Make Word K-Periodic LEETCODE WEEKLY CONTEST 396 SolutionJUST CODE · 0:38 · 400 views
3137. Minimum Number of Operations to Make Word K-Periodic (Leetcode Medium)Programming Live with Larry · 5:42 · 224 views
Leetcode 3137. Minimum Number of Operations to Make Word K-PeriodicElite Code · 26:16 · 143 views
3137. Minimum Number of Operations to Make Word K-Periodic Weekly Contest 396 Bangla solutionNazrul Islam Sajib · 14:15 · 35 views
3137. Minimum Number of Operations to Make Word K-Periodic || Best Intuition Approach Explained 🔥🔥Code With Anubhav · 43:03 · 25 views
The problem
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.
Approach overview
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 1: Character Frequency Counting
The main idea is to divide the word into segments of length k and consider each position in these segments. For each position, determine the most frequent character and calculate the changes needed to make all characters at this position the same across all segments. This involves minimal operations since you're replacing less frequent characters with the most frequent one.
Let's break it down: For each segment starting position, iterate over respective positions in each k-length chunk and count character frequencies. Then, for each position, find the maximum frequency character and derive the number of operations required to make all positions in that column identical by changing other characters to this one.
def min_operations(word, k):
n = len(word)
operations = 0
for i in range(k):
count = [0] * 26
for j in range(i, n, k):
count[ord(word[j]) - ord('a')] += 1
max_count = max(count)
operations += (n // k) - max_count
return operations
word = 'leetcodeleet'
k = 4
print(min_operations(word, k))import java.util.*;
public class KPeriodic {
public static int minOperations(String word, int k) {
int n = word.length();
int operations = 0;
for (int i = 0; i < k; i++) {
int[] count = new int[26];
for (int j = i; j < n; j += k) {
count[word.charAt(j) - 'a']++;
}
int maxCount = 0;
for (int c : count) {
if (c > maxCount) {
maxCount = c;
}
}
operations += (n / k) - maxCount;
}
return operations;
}
public static void main(String[] args) {
String word = "leetcodeleet";
int k = 4;
System.out.println(minOperations(word, k));
}
}#include <iostream>
#include <vector>
using namespace std;
int minOperations(string word, int k) {
int n = word.size();
int operations = 0;
for (int i = 0; i < k; ++i) {
vector<int> count(26, 0);
for (int j = i; j < n; j += k) {
count[word[j] - 'a']++;
}
int maxCount = 0;
for (int c = 0; c < 26; ++c) {
if (count[c] > maxCount) {
maxCount = count[c];
}
}
operations += (n / k) - maxCount;
}
return operations;
}
int main() {
string word = "leetcodeleet";
int k = 4;
cout << minOperations(word, k) << endl;
return 0;
}function minOperations(word, k) {
let n = word.length;
let operations = 0;
for (let i = 0; i < k; i++) {
let count = Array(26).fill(0);
for (let j = i; j < n; j += k) {
count[word.charCodeAt(j) - 97]++;
}
let maxCount = Math.max(...count);
operations += (n / k) - maxCount;
}
return operations;
}
console.log(minOperations('leetcodeleet', 4));#include <stdio.h>
#include <string.h>
int minOperations(char* word, int n, int k) {
int operations = 0;
for (int i = 0; i < k; i++) {
int count[26] = {0};
for (int j = i; j < n; j += k) {
count[word[j] - 'a']++;
}
int maxCount = 0;
for (int c = 0; c < 26; c++) {
if (count[c] > maxCount) {
maxCount = count[c];
}
}
operations += (n / k) - maxCount;
}
return operations;
}
int main() {
char word[] = "leetcodeleet";
int k = 4;
int n = strlen(word);
printf("%d\n", minOperations(word, n, k));
return 0;
}using System;
class KPeriodic {
public static int MinOperations(string word, int k) {
int n = word.Length;
int operations = 0;
for (int i = 0; i < k; i++) {
int[] count = new int[26];
for (int j = i; j < n; j += k) {
count[word[j] - 'a']++;
}
int maxCount = 0;
foreach (var c in count) {
if (c > maxCount) {
maxCount = c;
}
}
operations += (n / k) - maxCount;
}
return operations;
}
public static void Main() {
string word = "leetcodeleet";
int k = 4;
Console.WriteLine(MinOperations(word, k));
}
}In this Python function, the approach is analogous to the above languages. The main difference is the use of list comprehensions and the inherent library support for tracking sequences. The logic involves summing the changes necessary for uniformity across k-wise characters.
Time Complexity: O(n); Iterates through the whole string n times with constant operations within each section.
Space Complexity: O(1); Memory for frequency tracking remains constant.
Approach 2: Sliding Window Transform Technique
This approach focuses on shifting and comparing segments rather than counting & frequency evaluation. By shifting a window of k and observing minimal differences, you determine which characters to replace. This technique leverages direct comparisons and real-time tracking of mismatches along a sliding window of k.
The process involves shifting a k-length window placeholder and observing immediate next segment for mismatches. Operations are appended as needed to deal with non-conforming segments, assuming the primary reference is the initial segment.
def min_operations(word, k):
n = len(word)
operations = 0
for i in range(k):
count = [0] * 26
for j in range(i, n, k):
count[ord(word[j]) - ord('a')] += 1
max_count = max(count)
operations += (n // k) - max_count
return operations * k // n
word = 'leetcodeleet'
k = 4
print(min_operations(word, k))import java.util.*;
public class KPeriodic {
public static int minOperations(String word, int k) {
int n = word.length();
int operations = 0;
int[] counts = new int[26];
for (int i = 0; i < k; i++) {
Arrays.fill(counts, 0);
for (int j = i; j < n; j += k) {
counts[word.charAt(j) - 'a']++;
}
int maxCount = Arrays.stream(counts).max().getAsInt();
operations += (n / k) - maxCount;
}
return operations * k / n;
}
public static void main(String[] args) {
String word = "leetcodeleet";
int k = 4;
System.out.println(minOperations(word, k));
}
}#include <iostream>
#include <vector>
using namespace std;
int minOperations(string word, int k) {
vector<int> counts(26, 0);
int n = word.size(), operations = 0;
for (int i = 0; i < k; ++i) {
vector<int> current(26, 0);
for (int j = i; j < n; j += k) {
current[word[j] - 'a']++;
}
int max_count = *max_element(current.begin(), current.end());
operations += (n / k) - max_count;
}
return operations * k / n;
}
int main() {
string word = "leetcodeleet";
int k = 4;
cout << minOperations(word, k) << endl;
return 0;
}function minOperations(word, k) {
const n = word.length;
let operations = 0;
const count = Array(26).fill(0);
for (let i = 0; i < k; i++) {
count.fill(0);
for (let j = i; j < n; j += k) {
count[word.charCodeAt(j) - 97]++;
}
const maxCount = Math.max(...count);
operations += (n / k) - maxCount;
}
return operations * k / n;
}
console.log(minOperations('leetcodeleet', 4));#include <stdio.h>
#include <string.h>
int minOperations(char* word, int n, int k) {
int operations = 0;
for (int i = 0; i < k; i++) {
int current[26] = {0}, next[26] = {0};
for (int j = i; j < n; j += k) {
next[word[j] - 'a']++;
current[word[i] - 'a']++;
}
for(int c = 0; c < 26; c++) {
operations += (current[c] > next[c]) ? current[c] - next[c] : next[c] - current[c];
}
}
return operations / 2;
}
int main() {
char word[] = "leetcodeleet";
int k = 4;
int n = strlen(word);
printf("%d\n", minOperations(word, n, k));
return 0;
}using System;
class KPeriodic {
public static int MinOperations(string word, int k) {
int n = word.Length;
int operations = 0;
int[] counts = new int[26];
for (int i = 0; i < k; i++) {
Array.Clear(counts, 0, 26);
for (int j = i; j < n; j += k) {
counts[word[j] - 'a']++;
}
int maxCount = 0;
foreach (var c in counts) if (c > maxCount) maxCount = c;
operations += (n / k) - maxCount;
}
return operations * k / n;
}
public static void Main() {
string word = "leetcodeleet";
int k = 4;
Console.WriteLine(MinOperations(word, k));
}
}This Python approach applies the sliding window transformation rationale by gradually moving and checking section differences naturally in compact steps. Each k-segment functions as a micro-reference pivot-tier to then employ robust re-calculation toward uniform convergence efficiently.
Time Complexity: O(n); Takes a focused line-wise approach on sub-linear depths resulting in complete scanning ahead.
Space Complexity: O(1); Relief on integral inline usage for character set indexing.
Approach 3: Counting
We can divide the string word into substrings of length k, then count the occurrence of each substring, and finally return n/k minus the count of the most frequently occurring substring.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string word.
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Character Frequency Counting | Time Complexity: O(n); Iterates through the whole string n times with constant operations within each section. |
| Sliding Window Transform Technique | Time Complexity: O(n); Takes a focused line-wise approach on sub-linear depths resulting in complete scanning ahead. |
| Counting | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Number of Operations to Make Word K-Periodic easy or hard?
The problem is rated Medium because the implementation is simple once you recognize the pattern. The challenge lies in identifying that the string should be treated as k-sized blocks and that minimizing operations reduces to a frequency counting problem.
Minimum Number of Operations to Make Word K-Periodic Python/Java solution
Python and Java implementations both follow the same logic: iterate through the string in steps of k, extract each substring, and update its frequency in a dictionary or HashMap. After counting, compute totalBlocks minus the highest frequency. The solution runs in O(n) time.
How to solve Minimum Number of Operations to Make Word K-Periodic in O(n)?
Split the string into n/k substrings of length k and store their frequencies in a hash map. Track the substring with the maximum count. Since every other block must be converted to that substring, the answer is totalBlocks minus maxFrequency. Each substring is processed once, giving O(n) time complexity.
What is the best approach for Minimum Number of Operations to Make Word K-Periodic?
The optimal approach uses hash table frequency counting. Divide the string into substrings of length k, count how often each substring appears, and keep the most frequent one as the repeating pattern. The minimum operations equal total blocks minus the highest frequency. This runs in O(n) time with O(n) space.
Is Minimum Number of Operations to Make Word K-Periodic asked at Google/Amazon/Meta?
This problem follows common string-frequency and hash map patterns that frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving periodic strings, grouping substrings, or minimizing transformations are especially common in coding rounds.
What data structure is used in Minimum Number of Operations to Make Word K-Periodic?
A hash map (or dictionary) is the main data structure. It stores frequencies of each substring of length k. This allows constant-time updates and quick identification of the most frequent repeating block.
What is the time complexity of Minimum Number of Operations to Make Word K-Periodic?
The optimal solution runs in O(n) time where n is the length of the string. Each k-length substring is processed once and inserted into a hash map for counting. Space complexity is O(n) in the worst case if every block is unique.