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

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