3137. Minimum Number of Operations to Make Word K-Periodic

MediumHash TableStringCounting

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.

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".

Intuition

To solve this problem, we need to transform the given string word into a form where it can be expressed as multiple repetitions of a single substring of length k. Our goal is to determine the fewest number of operations needed to achieve this transformation.

The approach involves breaking down the string word into consecutive substrings each of length k. Once we have these substrings, we need to identify the most frequently occurring one. The key insight is that we can reduce the number of necessary operations by aiming to make all these substrings identical to the most common substring.

By counting the occurrences of each substring of length k, we determine which substring appears most often. The minimum number of operations required is then calculated as the total number of substrings (n / k) minus the count of the most frequently occurring substring. This calculation gives us the fewest changes needed to make all substrings the same, thereby making the entire string k-periodic.

Solution Approach

To tackle the problem, we employ a simple counting strategy. Here's a step-by-step breakdown of the algorithm used in the solution:

Divide the String into Substrings: We start by dividing the string word into several substrings, each of length k. These substrings are obtained at indices that are multiples of k.

Count Substring Occurrences: Utilize a Counter from the collections module in Python to count the frequency of each substring of length k.

from collections import Counter
count = Counter(word[i : i + k] for i in range(0, n, k))

Identify the Most Frequent Substring: Determine the maximum value from the Counter, which indicates how many times the most common substring appears.
```
max_frequency = max(count.values())
```
Calculate Minimum Operations: The minimum number of operations needed to make word k-periodic is given by the total number of substrings (n / k) minus the frequency of the most common substring. This gives the number of changes required to make all substrings identical.
```
min_operations = n // k - max_frequency
```

The algorithm is efficient, leveraging string manipulation and frequency counting within a single traversal of the string. By focusing on making all length k segments identical to the most frequent one, we minimize the number of operations needed for the transformation.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Suppose we have the string word = "ababacabab", and k = 3.

Divide the String into Substrings: First, divide word into substrings of length k=3 at indices 0, 3, 6, etc.
- Substrings: "aba", "bac", "aba"
Count Substring Occurrences: Use the Counter to count how frequently each substring appears.
- Count: {"aba": 2, "bac": 1}
Identify the Most Frequent Substring: Determine the substring with the maximum frequency.
- Most frequent substring: "aba" (appears 2 times)
Calculate Minimum Operations: Calculate the minimum number of operations needed to make word k-periodic. This is the total number of substrings minus the frequency of the most common substring:
- Total substrings = n / k = 9 / 3 = 3
- Min operations = 3 - 2 = 1

Thus, the minimum number of operations required to transform word into a k-periodic string is 1, which involves changing "bac" to "aba" so that all segments become "aba".

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
5        # Calculate the length of the input word
6        n = len(word)
7      
8        # Divide the word into k-length chunks and count occurrences of each unique chunk
9        chunks = [word[i : i + k] for i in range(0, n, k)]
10        chunk_count = Counter(chunks)
11      
12        # Identify the most frequent k-length chunk
13        max_occurrences = max(chunk_count.values())
14      
15        # Subtract the frequency of the most common chunk from the number of chunks to get the result
16        # The result represents the minimum operations needed to make the word k-periodic
17        return len(chunks) - max_occurrences
18

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public int minimumOperationsToMakeKPeriodic(String word, int k) {
6        // Create a map to store the frequency of each k-length substring.
7        Map<String, Integer> countMap = new HashMap<>();
8        int length = word.length();
9        int maxFrequency = 0;
10
11        // Iterate through the word, in steps of k, to get each k-length substring.
12        for (int i = 0; i < length; i += k) {
13            // Get the k-length substring starting at index i
14            String substring = word.substring(i, Math.min(i + k, length));
15          
16            // Update the frequency of the substring in the map.
17            int currentFrequency = countMap.getOrDefault(substring, 0) + 1;
18            countMap.put(substring, currentFrequency);
19
20            // Keep track of the maximum frequency encountered.
21            maxFrequency = Math.max(maxFrequency, currentFrequency);
22        }
23
24        // Calculate the minimum operations needed to make the word k-periodic.
25        return length / k - maxFrequency;
26    }
27}
28

1#include <string>
2#include <unordered_map>
3#include <algorithm> // For std::max
4
5class Solution {
6public:
7    // Function to calculate the minimum number of operations to make the string K-periodic
8    int minimumOperationsToMakeKPeriodic(std::string word, int k) {
9        std::unordered_map<std::string, int> countMap; // Map to count occurrences of each K-length substring
10        int wordLength = word.size(); // Get the length of the word
11        int maxFrequency = 0; // Track the maximum frequency of any K-length substring
12
13        // Iterate through the word, considering each K-length substring
14        for (int i = 0; i < wordLength; i += k) {
15            // Extract K-length substring starting at index i
16            std::string kSubstring = word.substr(i, k);
17          
18            // Increment the count of this substring in the map and update maxFrequency
19            maxFrequency = std::max(maxFrequency, ++countMap[kSubstring]);
20        }
21      
22        // Calculate and return the minimum number of operations required to make the string K-periodic
23        return wordLength / k - maxFrequency;
24    }
25};
26

1// Function to calculate the minimum operations required to make a string k-periodic
2function minimumOperationsToMakeKPeriodic(word: string, k: number): number {
3    // Map to store the frequency of k-sized substrings
4    const cnt: Map<string, number> = new Map();
5    // Length of the given word
6    const n: number = word.length;
7    // Variable to track the maximum frequency of any k-sized substring
8    let maxFrequency: number = 0;
9
10    // Iterate over the word with a step of k
11    for (let i = 0; i < n; i += k) {
12        // Extract the k-sized substring
13        const substring = word.slice(i, i + k);
14        // Update the frequency of the substring in the map
15        cnt.set(substring, (cnt.get(substring) || 0) + 1);
16        // Update the maximum frequency if the current substring's frequency is higher
17        maxFrequency = Math.max(maxFrequency, cnt.get(substring)!);
18    }
19
20    // Calculate and return the minimum number of operations needed
21    return Math.floor(n / k) - maxFrequency;
22}
23

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string word. This is because we iterate through the string in chunks of size k to form substrings, which results in a linear number of operations relative to the length of the string.

The space complexity is O(n), as we store all substrings of length k from the string word, which takes up space proportional to the length of the string.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know