Skip to content

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

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

 

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.

Solutions

Solution 1: Counting

Thinking

Each operation replaces one length-\(k\) block by another. The string should become a repetition of a single block. Trying every target block is proportional to the number of blocks.

The operation count is the number of blocks minus the frequency of the most common block. Counting is enough; the string need not be rewritten.

Slice \(word\) with step \(k\), take the maximum count, and return \(n/k\) minus that maximum.

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.

1
2
3
4
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())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minimumOperationsToMakeKPeriodic(word string, k int) int {
    cnt := map[string]int{}
    n := len(word)
    mx := 0
    for i := 0; i < n; i += k {
        s := word[i : i+k]
        cnt[s]++
        mx = max(mx, cnt[s])
    }
    return n/k - mx
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minimumOperationsToMakeKPeriodic(word: string, k: number): number {
    const cnt: Map<string, number> = new Map();
    const n: number = word.length;
    let mx: number = 0;
    for (let i = 0; i < n; i += k) {
        const s = word.slice(i, i + k);
        cnt.set(s, (cnt.get(s) || 0) + 1);
        mx = Math.max(mx, cnt.get(s)!);
    }
    return Math.floor(n / k) - mx;
}

Comments