Minimum Number of Operations to Make Word K-Periodic Solution In C++/Java/Python/Javascript
Problem Description
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. A string is k-periodic if there exists some string s of length k such that word can be obtained by concatenating s an arbitrary number of times.
Example
Input: word = "leetcodeleet", k = 4
Output: 1
Explanation:
To make word 4-periodic, we need to ensure that the string consists of repeated segments of length k = 4. The original string is "leetcodeleet", which can be divided into three substrings of length 4: "leet", "code", and "leet". To make it 4-periodic, all segments must be identical. We can replace "code" (starting at index 4) with "leet" (starting at index 0). After this replacement, the string becomes "leetleetleet", which is 4-periodic. Only 1 operation was required.
Input: word = "leetcoleet", k = 2
Output: 3
Explanation:
To make word 2-periodic, we need to ensure that every 2-character segment is identical throughout the string. The original string "leetcoleet" can be divided into five substrings of length 2: "le", "et", "co", "le", and "et". We need to transform all segments into a single repeating pattern. We apply the following operations: First, we pick i = 0 and j = 2, replacing the substring at i = 0 with the substring at j = 2, which changes the word to "etetcoleet". Next, we pick i = 4 and j = 0, replacing the substring at i = 4 with the substring at j = 0, updating the word to "etetetleet". Finally, we pick i = 6 and j = 0, replacing the substring at i = 6 with the substring at j = 0, resulting in "etetetetet". After 3 operations, the string becomes "etetetetet", which is 2-periodic. 3 operations were required to achieve this.
Constraints
1 <= n == word.length <= 10⁵
1 <= k <= word.length
k divides word.length.
word consists only of lowercase English letters.
The goal here is to transform the given word into a k-periodic string with the minimum number of operations. Since we can only swap k-length substrings at indices divisible by k, we need to determine the optimal way to align all segments to form a repeating pattern. Let’s explore how we can efficiently achieve this transformation!
Brute Force
Intuition
The brute force approach attempts to transform the given string into a k-periodic string by considering every possible way to modify the k-length substrings. The idea is to check all possible repeating patterns and determine the minimum number of operations required to make all k-length segments identical.
Instead of efficiently identifying the most frequent substring, this approach compares each segment with every other segment and replaces mismatched segments one by one. Since we can swap substrings at indices divisible by k, we repeatedly replace mismatched parts to form a uniform repeating pattern. Although this guarantees correctness, the approach is inefficient due to unnecessary comparisons and redundant operations.
Approach
Step 1: Extract k-Length Substrings
We first divide the given string into n/k substrings of length k. Each substring is stored in an array for further processing. Since k divides n, this ensures that each segment is of equal length.
Step 2: Try Every Substring as the Base Pattern
We assume each extracted substring can be the repeating pattern. For each candidate pattern, we iterate through the list of substrings and count how many replacements are needed to make all substrings identical to the chosen base pattern.
Step 3: Calculate the Minimum Number of Operations
For every candidate base pattern, we compute the number of mismatches across all substrings. The number of replacements required is equal to the count of substrings that do not match the chosen base pattern. We track the minimum value among all possibilities.
Step 4: Return the Minimum Transformations
After testing all possible base patterns, the result is the minimum number of replacements required to make the string k-periodic. This brute force method ensures correctness but is inefficient due to unnecessarily repeated comparisons, making it impractical for large input sizes.
Let us understand this with a video,
Minimum Number of Operations to Make Word K-Periodic-Brute-Force-Approach
Dry Run
Input:
The given string is leetcoleet with k = 2. This means we need to divide the string into substrings of length k and then find the minimum number of replacements needed to make all the substrings identical.
Output:
The minimum number of operations required is 3.
Step 1: Extract k-Length Substrings
Since k = 2, we divide the given string into equal-sized substrings. The total number of such substrings can be calculated using the formula n / k, where n is the length of the given word. The length of leetcoleet is 10, so the total number of segments is 10 / 2 = 5.
Extracting substrings from the given string, we get:
At index i = 0, the substring is "le", which consists of the first two characters "l" and "e".
At index i = 2, the substring is "et", which consists of the characters "e" and "t".
At index i = 4, the substring is "co", which consists of the characters "c" and "o".
At index i = 6, the substring is "le", which consists of the characters "l" and "e".
At index i = 8, the substring is "et", which consists of the characters "e" and "t".
The extracted substrings are ["le", "et", "co", "le", "et"].
Step 2: Try Every Substring as the Base Pattern
To make the string k-periodic, we assume that each unique substring could be the repeating unit and then count how many changes are needed to make all substrings match this assumed pattern.
Assuming "le" as the base pattern, we compare it with all other substrings in the list. The first substring is already "le", so no change is needed. The second substring is "et", which is different from "le", so it needs to be replaced with "le". The third substring is "co", which is also different, so it needs to be changed to "le". The fourth substring is already "le", so no change is required. The fifth substring is "et", which again needs to be replaced with "le". In total, three replacements are required to make the entire list ["le", "le", "le", "le", "le"]. Thus, the number of operations required when choosing "le" as the base pattern is 3.
Now, assuming "et" as the base pattern, the first substring "le" needs to be replaced with "et". The second substring "et" is already correct, so no change is needed. The third substring "co" needs to be replaced with "et". The fourth substring "le" must also be replaced with "et". The fifth substring "et" is already correct, so no modification is needed. The final modified sequence would be ["et", "et", "et", "et", "et"]. Again, the total number of replacements required is 3.
Finally, assuming "co" as the base pattern, the first substring "le" needs to be changed to "co". The second substring "et" must also be changed to "co". The third substring "co" is already correct, so no replacement is needed. The fourth substring "le" must be changed to "co", and the fifth substring "et" must also be modified to "co". The final sequence becomes ["co", "co", "co", "co", "co"]. The total number of replacements required is 4.
Step 3: Compute the Minimum Operations
The number of replacements required for each assumed base pattern is calculated as follows:
If "le" is chosen as the base pattern, the number of operations required is 3.
If "et" is chosen as the base pattern, the number of operations required is 3.
If "co" is chosen as the base pattern, the number of operations required is 4.
Since we are looking for the minimum number of replacements, the final answer is the minimum among 3, 3, and 4, which is 3.
Final Output:
The minimum number of operations required to make the given string leetcoleet a k-periodic string for k = 2 is 3.
Code for All Languages
C++
//Minimum Number of Operations to Make Word K-Periodic - Brute force Approach - C++
int minimumOperationsBruteForce(string word, int k) {
int n = word.length();
int totalSegments = n / k;
vector<string> substrings;
// Step 1: Extract k-length substrings
for (int i = 0; i < n; i += k) {
substrings.push_back(word.substr(i, k));
}
int minOperations = INT_MAX;
// Step 2: Try each unique substring as the base pattern
for (int i = 0; i < totalSegments; i++) {
string basePattern = substrings[i];
int operations = 0;
// Count how many substrings need to be changed
for (int j = 0; j < totalSegments; j++) {
if (substrings[j] != basePattern) {
operations++;
}
}
// Step 3: Compute the minimum operations
minOperations = min(minOperations, operations);
}
return minOperations;
}Java
//Minimum Number of Operations to Make Word K-Periodic - Brute force Approach - Java
import java.util.*;
class Solution {
public int minimumOperationsBruteForce(String word, int k) {
int n = word.length();
int totalSegments = n / k;
List<String> substrings = new ArrayList<>();
// Step 1: Extract k-length substrings
for (int i = 0; i < n; i += k) {
substrings.add(word.substring(i, i + k));
}
int minOperations = Integer.MAX_VALUE;
// Step 2: Try each unique substring as the base pattern
for (int i = 0; i < totalSegments; i++) {
String basePattern = substrings.get(i);
int operations = 0;
// Count how many substrings need to be changed
for (int j = 0; j < totalSegments; j++) {
if (!substrings.get(j).equals(basePattern)) {
operations++;
}
}
// Step 3: Compute the minimum operations
minOperations = Math.min(minOperations, operations);
}
return minOperations;
}
}Python
#Minimum Number of Operations to Make Word K-Periodic - Brute force Approach - Python
import sys
from itertools import combinations
def minimum_operations_brute_force(word: str, k: int) -> int:
n = len(word)
total_segments = n // k
substrings = [word[i:i + k] for i in range(0, n, k)]
min_operations = float('inf')
# Step 2: Try each unique substring as the base pattern
for base_pattern in substrings:
operations = sum(1 for substring in substrings if substring != base_pattern)
min_operations = min(min_operations, operations)
return min_operationsJavascript
//Minimum Number of Operations to Make Word K-Periodic - Brute force Approach - Javascript
function minimumOperationsBruteForce(word, k) {
const n = word.length;
const totalSegments = Math.floor(n / k);
const substrings = [];
// Step 1: Extract k-length substrings
for (let i = 0; i < n; i += k) {
substrings.push(word.substring(i, i + k));
}
let minOperations = Infinity;
// Step 2: Try each unique substring as the base pattern
for (let basePattern of substrings) {
let operations = substrings.filter(substring => substring !== basePattern).length;
minOperations = Math.min(minOperations, operations);
}
return minOperations;
}Time Complexity O(n^2/k)
The brute force approach iterates through all possible k-length substrings of the given string and considers each substring as a potential base pattern. For each base pattern, it scans through all k-length segments to count the number of replacements needed. Extracting k-length substrings takes O(n) time, and for each of the n/k substrings, we perform an O(n/k) comparison to determine the number of necessary changes. This results in an overall time complexity of O((n/k)²) = O(n²/k²). Since k is a divisor of n, this can be simplified to O(n²/k) in practical cases. However, this is inefficient for large inputs, making it infeasible when n is significantly large.
Space Complexity - O (n/k)
The primary data structure used in the brute force approach is a list (or array) that stores all k-length substrings extracted from the input word. Since there are n/k substrings, the space complexity for storing these substrings is O(n/k). Additionally, only a few integer variables are used to track counts, which contribute O(1) space usage. Thus, the total space complexity is O(n/k), which is relatively efficient compared to the time complexity but still grows linearly with the input size. This makes the algorithm memory-efficient but computationally expensive for large strings.
Bridge between Brute force and Optimized approach
The brute force approach, while conceptually simple, is inefficient as it manually compares and transforms substrings without leveraging any patterns. To optimize this, we shift our focus to pattern recognition and frequency analysis. Instead of checking every k-length substring individually, we use a hash map to count occurrences of each substring. This allows us to quickly determine the most frequent substring and compute the minimum replacements needed in a single pass.
By replacing exhaustive comparisons with frequency-based insights, we eliminate redundant computations and achieve a more scalable solution. This transformation significantly improves efficiency, making it feasible for large input sizes without compromising correctness.
Optimized Approach
Intuition
The code segments the given string into k-periodic substrings, counts the occurrences of each unique substring, and determines the minimum number of operations required to make the entire string k-periodic. The primary goal is to identify the most frequently occurring substring and modify all other substrings to match it.
To achieve this, the code first divides the string into n/k segments, where each segment has a length of k. A hash map is used to store the frequency of each substring. Once all substring frequencies are recorded, the algorithm finds the most common substring (the one with the highest frequency). Since all segments must be identical in a k-periodic string, the minimum number of operations required is the total number of segments minus the frequency of the most common substring. This ensures that all other segments are replaced to match the dominant substring.
Approach
Step 1: Initialize a Map to Track Substring Frequency
We start by creating a hash map to keep track of the occurrences of each k-length substring in the given string. This map will help us determine the most frequently occurring substring, which will be used to minimize the number of operations needed.
Step 2: Divide the String into k-Periodic Substrings
Since the problem guarantees that k divides n, we iterate through the string in steps of k, extracting substrings of length k. Each substring is stored in the map, with its frequency count incremented. This helps in identifying the most frequently appearing substring.
Step 3: Determine the Most Frequent Substring
After processing all substrings, we scan the map to find the maximum frequency of any substring. This represents the substring that appears the most times in the current arrangement of word.
Step 4: Calculate the Minimum Operations Required
The total number of k-periodic substrings in the word is n/k. To make the word fully k-periodic, all substrings must match the most frequent one. The minimum number of operations required is calculated as:
total k-periodic substrings−maximum frequency of any substring\text{total k-periodic substrings} - \text{maximum frequency of any substring}total k-periodic substrings−maximum frequency of any substring
This gives us the number of replacements needed to convert all substrings into the most frequent one, ensuring the string becomes k-periodic.
Let us understand this with a video,
Minimum Number of Operations to Make Word K-Periodic-Optimal-Approach
Dry Run
Input:
word = "leetcodeleet", k = 4
Output: 1
Step 1: Initialize Data Structures
We create a hash map to store substring frequencies. We also calculate the number of k-length substrings:
- n = 12, k = 4
- totalSegments = n / k = 12 / 4 = 3
- Initialize an empty map to track substring occurrences.
Step 2: Extract k-Length Substrings and Populate the Map
We iterate through word, extracting substrings of length k = 4 and updating the frequency map.
- i = 0 → Substring = "leet" → map = {"leet": 1}
- i = 4 → Substring = "code" → map = {"leet": 1, "code": 1}
- i = 8 → Substring = "leet" → map = {"leet": 2, "code": 1}
Step 3: Find the Most Frequent Substring
We scan the map to find the substring with the highest frequency:
- "leet" appears 2 times
- "code" appears 1 time
- Max frequency = 2
Step 4: Compute the Minimum Operations
Total k-length substrings = 3.
The most frequent substring appears 2 times.
We need to replace the remaining substring(s) to match the most frequent one.
Operations=totalSegments−maxFrequency=3−2=1\text{Operations} = \text{totalSegments} - \text{maxFrequency} = 3 - 2 = 1Operations=totalSegments−maxFrequency=3−2=1
So, the minimum number of operations required is 1.
Final Output:
1
Code for All Languages
C++
//Minimum Number of Operations to Make Word K-Periodic - Optimized Approach - Cpp
int minimumOperationsToMakeKPeriodic(string word, int k) {
int n = word.length();
unordered_map<string, int> freqMap;
int totalSegments = n / k;
// Step 2: Extract k-length substrings and populate the map
for (int i = 0; i < n; i += k) {
string substring = word.substr(i, k);
freqMap[substring]++;
}
// Step 3: Find the most frequent substring
int maxFrequency = 0;
for (auto &entry : freqMap) {
maxFrequency = max(maxFrequency, entry.second);
}
// Step 4: Compute the minimum operations
return totalSegments - maxFrequency;
}Java
//Minimum Number of Operations to Make Word K-Periodic - Optimized Approach - java
import java.util.*;
class Solution {
public int minimumOperationsToMakeKPeriodic(String word, int k) {
int n = word.length();
Map<String, Integer> freqMap = new HashMap<>();
int totalSegments = n / k;
// Step 2: Extract k-length substrings and populate the map
for (int i = 0; i < n; i += k) {
String substring = word.substring(i, i + k);
freqMap.put(substring, freqMap.getOrDefault(substring, 0) + 1);
}
// Step 3: Find the most frequent substring
int maxFrequency = 0;
for (int frequency : freqMap.values()) {
maxFrequency = Math.max(maxFrequency, frequency);
}
// Step 4: Compute the minimum operations
return totalSegments - maxFrequency;
}
}Python
#Minimum Number of Operations to Make Word K-Periodic - Optimized Approach - Python
from collections import Counter
def minimum_operations_to_make_k_periodic(word: str, k: int) -> int:
n = len(word)
total_segments = n // k
# Step 2: Extract k-length substrings and populate the frequency map
freq_map = Counter(word[i:i+k] for i in range(0, n, k))
# Step 3: Find the most frequent substring
max_frequency = max(freq_map.values())
# Step 4: Compute the minimum operations
return total_segments - max_frequencyJavascript
//Minimum Number of Operations to Make Word K-Periodic - Optimized Approach - Javascript
function minimumOperationsToMakeKPeriodic(word, k) {
const n = word.length;
const totalSegments = Math.floor(n / k);
// Step 2: Extract k-length substrings and populate the frequency map
const freqMap = new Map();
for (let i = 0; i < n; i += k) {
const substring = word.substring(i, i + k);
freqMap.set(substring, (freqMap.get(substring) || 0) + 1);
}
// Step 3: Find the most frequent substring
let maxFrequency = 0;
for (const count of freqMap.values()) {
maxFrequency = Math.max(maxFrequency, count);
}
// Step 4: Compute the minimum operations
return totalSegments - maxFrequency;
}
Time Complexity- Minimum Number of Operations to Make Word K-Periodic - O(n)
The time complexity of the solution is O(n), where n is the length of the string. Extracting k-length substrings takes O(n) time since we iterate through the string in steps of k and store frequencies in a hashmap with O(1) operations. Finding the most frequent substring and computing the required replacements both take O(n/k), which simplifies to O(n) overall.
The space complexity is O(n/k) in the worst case, where all substrings are unique. This approach efficiently determines the minimum operations needed by leveraging frequency counts instead of modifying the string directly, making it well-suited for large inputs up to 10⁵ characters.
Space Complexity - Minimum Number of Operations to Make Word K-Periodic - O(n/k)
The space complexity of this solution is O(n/k) in the worst case. This arises because we use a hash map to store the frequencies of k-length substrings. Since we extract n/k substrings from the string, the maximum number of unique keys in the hash map is n/k. If every k-length substring is unique, the hash map will contain n/k entries, leading to an O(n/k) space requirement. However, in cases where many substrings are identical, the space usage is lower.
Apart from the hash map, the solution only uses a few integer variables, such as n, k, totalSegments, and maxFrequency, all of which require O(1) space. There are no additional data structures or recursive calls that contribute to extra memory usage. Therefore, while the space complexity depends on the number of unique substrings, it remains efficient, making this approach well-optimized for handling large inputs.
Similar Problems
Find the Maximum character that repeat in the given substring
Detect the pattern of length where there is M repeated K or may be more