Leetcode 3137: Minimum Number of Operations to Make Word K-Periodic
You are given a string
word of length n, and an integer k such that k divides n. In one operation, you can pick any two indices i and j, both divisible by k, and swap the substrings starting from i and j, each of length k. The goal is to transform word into a k-periodic string, meaning that the string can be represented as multiple concatenations of a substring of length k. Your task is to determine the minimum number of operations required to make the string k-periodic.Problem
Approach
Steps
Complexity
Input: The input consists of a string `word` and an integer `k`.
Example: Example 1:
Input: word = "abcdefabcdef", k = 3
Output: 1
Constraints:
• 1 <= n == word.length <= 10^5
• 1 <= k <= word.length
• k divides word.length.
• word consists only of lowercase English letters.
Output: Return the minimum number of operations required to make the word `k`-periodic.
Example: Example 1:
Input: word = "abcdefabcdef", k = 3
Output: 1
Constraints:
• The result must be an integer representing the minimum number of operations.
Goal: The goal is to make the word `k`-periodic with the fewest number of substring swaps.
Steps:
• For each block of size `k` in the string, group the substrings and count how many times each substring appears.
• The fewer the number of unique substrings in the blocks, the fewer the swaps needed to make the word periodic.
• To minimize the operations, swap the most frequent substrings to align the other blocks.
Goal: The constraints for the word and integer k are defined below.
Steps:
• 1 <= n == word.length <= 10^5
• 1 <= k <= word.length
• k divides word.length.
• word consists only of lowercase English letters.
Assumptions:
• The string consists only of lowercase English letters.
• The value of k divides the length of the string.
• Input: Example 1:
• Explanation: In the word 'abcdefabcdef' with k=3, there are two substrings 'abc' and 'def'. Since they repeat, we need just one operation to make the word periodic by swapping the second 'abc' with the first 'def'.
• Input: Example 2:
• Explanation: In the word 'aabbccaabbcc' with k=2, there are three unique substrings: 'aa', 'bb', and 'cc'. We need to swap substrings to make them align, requiring 3 operations.
Approach: To solve this problem, we need to count the frequency of substrings of length k and minimize the number of operations required to make the string k-periodic.
Observations:
• The solution involves counting the frequency of each substring and minimizing the operations based on these frequencies.
• A greedy approach could help by choosing the most frequent substrings to minimize the number of swaps.
Steps:
• Create a map to store the frequency of each substring of length k.
• Iterate through the string to count the occurrences of each substring of length k.
• Find the most frequent substring, and calculate how many operations are needed to align the other substrings.
• Return the minimum number of operations.
Empty Inputs:
• The problem guarantees that the length of the word is at least 1.
Large Inputs:
• The solution must efficiently handle inputs where the length of the word is up to 100,000.
Special Values:
• Ensure that the solution works when there are multiple unique substrings or when all substrings are the same.
Constraints:
• Ensure that k divides the length of the word.
int minimumOperationsToMakeKPeriodic(string s, int k) {
int n = s.size();
map<string, int> mp;
for(int i = 0; i < n / k; i++) {
mp[s.substr(i * k, k)]++;
}
int lg = 0, net = 0;
for(auto it: mp) {
lg = max(lg, it.second);
net += it.second;
}
return net - lg;
}
1 : Function Definition
int minimumOperationsToMakeKPeriodic(string s, int k) {
Defines the function `minimumOperationsToMakeKPeriodic`, which takes a string `s` and an integer `k` to determine the minimum number of operations required to make the string periodic with period `k`.
2 : Variable Initialization
int n = s.size();
Initializes `n` to the length of the string `s` to help in determining the range for substring operations.
3 : Map Initialization
map<string, int> mp;
Initializes a map `mp` to store substrings of length `k` as keys and their corresponding frequency as values.
4 : Loop Structure
for(int i = 0; i < n / k; i++) {
Starts a loop that iterates through the string `s`, dividing it into segments of length `k`.
5 : Map Update
mp[s.substr(i * k, k)]++;
For each substring of length `k` starting at index `i * k`, it updates the frequency count in the map `mp`.
6 : Variable Initialization
The next block of code initializes variables for calculating the final result.
7 : Variable Initialization
int lg = 0, net = 0;
Initializes two integer variables: `lg` to store the largest frequency of any substring, and `net` to store the total number of substrings.
8 : Iteration Over Map
for(auto it: mp) {
Starts a loop to iterate through the map `mp`, which contains the frequencies of substrings.
9 : Max Frequency Update
lg = max(lg, it.second);
Updates `lg` with the maximum frequency of any substring in the map.
10 : Net Frequency Update
net += it.second;
Adds the frequency of the current substring to the total count `net`.
11 : Return Statement
return net - lg;
Returns the result of `net - lg`, which represents the minimum number of operations needed to make the string periodic.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, where n is the length of the word, since we iterate over the string and process substrings of length k.
Best Case: O(1)
Worst Case: O(n/k)
Description: The space complexity is linear in terms of the number of distinct substrings of length k, which is O(n/k).
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus