# Minimum Number of Operations to Make Word K-Periodic
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-word-k-periodic
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Turing](https://scaleengineer.com/companies/turing)
---
## 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 <= 105`
* `1 <= k <= word.length`
* `k` divides `word.length`.
* `word` consists only of lowercase English letters.

# Approaches
## Brute-Force Counting with Nested Loops
This approach involves first extracting all the k-length substrings and then using a brute-force method with nested loops to find the frequency of each substring. The goal is to identify the substring that appears most often, which will be the target for making the word k-periodic.
**Time:** O(n^2 / k). Let `m = n/k` be the number of substrings. Extracting all substrings takes `m * k = O(n)` time. The nested loops run `m * m` times. Inside the inner loop, string comparison takes `O(k)` time. So, the counting part is `O(m^2 * k) = O((n/k)^2 * k) = O(n^2 / k)`. The total time is dominated by the counting part. · **Space:** O(n). We store `m = n/k` substrings, each of length `k`. The total space required for the list is `m * k = O(n)`.
**Pros:** Simple to understand and implement.; It doesn't require complex data structures.
**Cons:** Inefficient for large inputs due to the quadratic time complexity relative to the number of substrings.; Can lead to 'Time Limit Exceeded' on platforms with large test cases.
### Explanation
The algorithm starts by dividing the input string `word` into `n/k` non-overlapping substrings, each of length `k`. These substrings are stored in a list. Then, it iterates through this list of substrings. For each substring, it performs another iteration through the entire list to count how many times it appears. A variable `maxFrequency` keeps track of the highest frequency found so far. After checking each substring, `maxFrequency` is updated if the current substring's frequency is higher. Once the most frequent substring and its count (`maxFrequency`) are determined, the minimum number of operations can be calculated. The total number of substrings is `n/k`. To make the word k-periodic, we want to make all substrings identical to the most frequent one. The number of substrings that already match is `maxFrequency`. Therefore, the number of substrings that need to be changed (which corresponds to the number of operations) is `(n/k) - maxFrequency`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int n = word.length();
        int numSubstrings = n / k;
        if (numSubstrings <= 1) {
            return 0;
        }

        List<String> substrings = new ArrayList<>();
        for (int i = 0; i < n; i += k) {
            substrings.add(word.substring(i, i + k));
        }

        int maxFrequency = 0;
        for (int i = 0; i < numSubstrings; i++) {
            int currentFrequency = 0;
            for (int j = 0; j < numSubstrings; j++) {
                if (substrings.get(i).equals(substrings.get(j))) {
                    currentFrequency++;
                }
            }
            maxFrequency = Math.max(maxFrequency, currentFrequency);
        }

        return numSubstrings - maxFrequency;
    }
}
```
### Algorithm
1. Calculate the total number of k-length substrings, `m = n / k`.
2. Create a list to store all these `m` substrings.
3. Iterate from `i = 0` to `n-1` with a step of `k`. In each step, extract `word.substring(i, i + k)` and add it to the list.
4. Initialize `maxFrequency = 0`.
5. Iterate through the list of substrings with an outer loop (let's say index `i`).
6. Inside the outer loop, initialize `currentFrequency = 0`.
7. Start an inner loop (index `j`) to compare the substring at index `i` with all other substrings in the list.
8. If `substrings.get(i)` is equal to `substrings.get(j)`, increment `currentFrequency`.
9. After the inner loop finishes, update `maxFrequency = Math.max(maxFrequency, currentFrequency)`.
10. After the outer loop finishes, the result is `m - maxFrequency`.

## Sorting-Based Frequency Counting
An intermediate approach between brute-force and a hash map involves sorting the substrings. By sorting, all identical substrings become adjacent, making it easy to count the frequency of the most common one in a single pass.
**Time:** O(n * log(n/k)). Let `m = n/k`. Extracting substrings takes `O(n)`. Sorting a list of `m` strings, where each comparison takes `O(k)`, results in a time complexity of `O(m * log(m) * k)`. This simplifies to `O((n/k) * log(n/k) * k) = O(n * log(n/k))`. The final pass to count frequencies takes `O(m * k) = O(n)`. The sorting step dominates. · **Space:** O(n). We need to store `m = n/k` substrings of length `k`, which amounts to `m * k = O(n)` space.
**Pros:** More efficient than the brute-force approach.; Conceptually simple, relying on a standard sorting algorithm.
**Cons:** Slower than the hash map approach.; Requires `O(n)` auxiliary space, similar to the other approaches.
### Explanation
Similar to the brute-force approach, this method begins by extracting all `n/k` k-length substrings into a list. The key difference is that instead of using nested loops, we sort this list of substrings lexicographically. After sorting, all occurrences of the same substring will be grouped together. We can then iterate through the sorted list once to find the longest contiguous block of identical substrings. The length of this block is the `maxFrequency`. For example, if the substrings are `["c", "a", "c", "b", "c"]`, after sorting they become `["a", "b", "c", "c", "c"]`. A single pass can find that "c" appears 3 times, which is the maximum frequency. Finally, the result is calculated as `(n/k) - maxFrequency`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int n = word.length();
        int numSubstrings = n / k;
        if (numSubstrings <= 1) {
            return 0;
        }

        List<String> substrings = new ArrayList<>();
        for (int i = 0; i < n; i += k) {
            substrings.add(word.substring(i, i + k));
        }

        Collections.sort(substrings);

        int maxFrequency = 1;
        int currentFrequency = 1;
        for (int i = 1; i < numSubstrings; i++) {
            if (substrings.get(i).equals(substrings.get(i - 1))) {
                currentFrequency++;
            } else {
                currentFrequency = 1;
            }
            maxFrequency = Math.max(maxFrequency, currentFrequency);
        }
        
        return numSubstrings - maxFrequency;
    }
}
```
### Algorithm
1. Calculate the total number of k-length substrings, `m = n / k`.
2. Create a list and populate it with all `m` substrings from the `word`.
3. Sort the list of substrings.
4. Initialize `maxFrequency = 1` and `currentFrequency = 1` (assuming `m > 0`).
5. Iterate through the sorted list from the second element (`i = 1`).
6. Compare the current substring `substrings.get(i)` with the previous one `substrings.get(i-1)`.
7. If they are the same, increment `currentFrequency`.
8. If they are different, reset `currentFrequency` to 1.
9. In each step, update `maxFrequency = Math.max(maxFrequency, currentFrequency)`.
10. After the loop, the result is `m - maxFrequency`.

## Using a Hash Map for Frequency Counting
The most efficient approach is to use a hash map (or a dictionary) to count the frequencies of each unique k-length substring. This avoids both nested loops and sorting, reducing the time complexity to linear.
**Time:** O(n). Let `m = n/k` be the number of substrings. The loop runs `m` times. Inside the loop, `substring()` takes `O(k)` time, and hash map operations (get, put) take an average of `O(k)` time (due to key hashing and comparison). The total time is `m * O(k) = (n/k) * O(k) = O(n)`. · **Space:** O(n). In the worst-case scenario, all `m = n/k` substrings are unique. Storing them in the hash map requires space proportional to the total length of all unique substrings, which is at most `m * k = O(n)`.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for the given constraints.
**Cons:** Uses extra space for the hash map, which can be significant if the number of unique substrings is large.
### Explanation
The core idea is to find the most frequent k-length substring and make all other substrings identical to it. The number of operations will be the total number of substrings minus the frequency of the most common one. The algorithm iterates through the `word` in steps of `k`, extracting each k-length substring. For each extracted substring, it uses a hash map to store and update its frequency count. The substring itself is the key, and its frequency is the value. While populating the hash map, we can also keep track of the maximum frequency seen so far. This avoids a separate pass through the map's values later. After iterating through all substrings, we will have the count of the most frequent one (`maxFrequency`). The total number of substrings is `n/k`. The minimum number of operations is then `(n/k) - maxFrequency`. This is because we keep the `maxFrequency` substrings that are already the desired pattern and change the rest.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int n = word.length();
        Map<String, Integer> frequencyMap = new HashMap<>();
        int maxFrequency = 0;

        for (int i = 0; i < n; i += k) {
            String sub = word.substring(i, i + k);
            int currentFrequency = frequencyMap.getOrDefault(sub, 0) + 1;
            frequencyMap.put(sub, currentFrequency);
            maxFrequency = Math.max(maxFrequency, currentFrequency);
        }

        int numSubstrings = n / k;
        return numSubstrings - maxFrequency;
    }
}
```
### Algorithm
1. Initialize a hash map, `Map<String, Integer> frequencyMap`, to store the frequency of each substring.
2. Initialize `maxFrequency = 0`.
3. Calculate the total number of substrings, `m = n / k`.
4. Iterate from `i = 0` to `n-1` with a step of `k`.
5. In each step, extract the substring `s = word.substring(i, i + k)`.
6. Update the frequency of `s` in the `frequencyMap`. `frequencyMap.put(s, frequencyMap.getOrDefault(s, 0) + 1)`.
7. After updating, get the new frequency of `s` and update `maxFrequency = Math.max(maxFrequency, newFrequency)`.
8. After the loop, the result is `m - maxFrequency`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumOperationsToMakeKPeriodic(string word, int k) {
    unordered_map<string, int> cnt;
    int n = word.size();
    int mx = 0;
    for (int i = 0; i < n; i += k) {
      mx = max(mx, ++cnt[word.substr(i, k)]);
    }
    return n / k - mx;
  }
};

```

### Python

```python
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())

```