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 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.
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.
This C solution implements the character frequency counting approach. It first initializes an operations counter and iterates over each position in a k-length segment. It counts the frequency of each character appearing at the same position in different segments using an array of size 26 (one element for each letter). It then finds the maximum frequency among these counts to calculate the minimal number of changes needed.
Time Complexity: O(n); As we iterate over each character position about n / k times and then check 26 possible characters, this simplifies to O(n) operations.
Space Complexity: O(1); The space complexity is constant as we use a fixed array of size 26 to store character counts.
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.
This C solution uses two arrays per k-segment to track character distribution. For each index within k, it determines mismatch operations by comparing shifts. By focusing directly on segment mismatches, it simplifies the character change consideration through binary-like influence segment comparison.
Time Complexity: O(n); Doing multi-segment checks still involves direct traversals of the original string.
Space Complexity: O(1); Utilizes fixed-size arrays.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Character Frequency Counting | Time Complexity: O(n); As we iterate over each character position about n / k times and then check 26 possible characters, this simplifies to O(n) operations. |
| Sliding Window Transform Technique | Time Complexity: O(n); Doing multi-segment checks still involves direct traversals of the original string. |
| Counting | — |
| 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. |
3137. Minimum Number of Operations to Make Word K-Periodic | Hash Map • Aryan Mittal • 1,309 views views
Watch 7 more video solutions →Practice Minimum Number of Operations to Make Word K-Periodic with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor