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

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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 <= 10^5
  • 1 <= k <= word.length
  • k divides word.length.
  • word consists only of lowercase English letters.

Solution

Method 1 – Greedy Counting of k-Substrings

Intuition

To make the word k-periodic, all k-length blocks must be the same. We can count the frequency of each k-length substring and find the most common one. The minimum operations is the number of blocks minus the count of the most common block.

Approach

  1. Split the word into n // k blocks of length k.
  2. Count the frequency of each block.
  3. The answer is total blocks minus the frequency of the most common block.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int minimumOperations(string word, int k) {
        int n = word.size(), blocks = n / k;
        unordered_map<string, int> freq;
        for (int i = 0; i < n; i += k)
            freq[word.substr(i, k)]++;
        int maxf = 0;
        for (auto& [s, f] : freq) maxf = max(maxf, f);
        return blocks - maxf;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func minimumOperations(word string, k int) int {
    n := len(word)
    blocks := n / k
    freq := map[string]int{}
    for i := 0; i < n; i += k {
        freq[word[i:i+k]]++
    }
    maxf := 0
    for _, f := range freq {
        if f > maxf {
            maxf = f
        }
    }
    return blocks - maxf
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.*;
class Solution {
    public int minimumOperations(String word, int k) {
        int n = word.length(), blocks = n / k;
        Map<String, Integer> freq = new HashMap<>();
        for (int i = 0; i < n; i += k)
            freq.put(word.substring(i, i + k), freq.getOrDefault(word.substring(i, i + k), 0) + 1);
        int maxf = 0;
        for (int f : freq.values()) maxf = Math.max(maxf, f);
        return blocks - maxf;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minimumOperations(word: String, k: Int): Int {
        val n = word.length; val blocks = n / k
        val freq = mutableMapOf<String, Int>()
        for (i in 0 until n step k) {
            val sub = word.substring(i, i + k)
            freq[sub] = freq.getOrDefault(sub, 0) + 1
        }
        val maxf = freq.values.maxOrNull() ?: 0
        return blocks - maxf
    }
}
1
2
3
4
5
6
7

class Solution:
    def minimumOperations(self, word: str, k: int) -> int:
        n = len(word)
        blocks = n // k
        from collections import Counter
        freq = Counter(word[i:i+k] for i in range(0, n, k))
        return blocks - max(freq.values())
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

use std::collections::HashMap;
impl Solution {
    pub fn minimum_operations(word: String, k: i32) -> i32 {
        let n = word.len();
        let k = k as usize;
        let blocks = n / k;
        let mut freq = HashMap::new();
        let w = word.as_bytes();
        for i in (0..n).step_by(k) {
            let sub = &w[i..i + k];
            *freq.entry(sub).or_insert(0) += 1;
        }
        let maxf = freq.values().max().copied().unwrap_or(0);
        (blocks as i32) - maxf
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    minimumOperations(word: string, k: number): number {
        const n = word.length, blocks = n / k;
        const freq = new Map<string, number>();
        for (let i = 0; i < n; i += k) {
            const sub = word.slice(i, i + k);
            freq.set(sub, (freq.get(sub) ?? 0) + 1);
        }
        let maxf = 0;
        for (const f of freq.values()) maxf = Math.max(maxf, f);
        return blocks - maxf;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of word, single pass.
  • 🧺 Space complexity: O(n // k) — for substring frequency map.