Minimum Number of Operations to Make Word K-Periodic

Medium
1816.

Minimum Number of Operations to Make Word K-Periodic

Minimum Number of Operations to Make Word K-Periodic is a medium coding problem on strings, hash table and counting, asked in Google interviews.

You are given a string word of length n and an integer k that divides n.

In one operation you pick two indices i and j, both divisible by k, and replace the length-k substring starting at i with the length-k substring starting at j — that is, word[i..i + k - 1] becomes a copy of word[j..j + k - 1].

The word is k-periodic if it equals some length-k string s repeated n / k times (for example, "ababab" is 2-periodic with s = "ab"). Return the minimum number of operations needed to make word k-periodic.

Example 1

Input
word = "codekatacode", k = 4
Output
1
Explanation
Copy the block at index 0 over `kata`, giving `codecodecode`.

Example 2

Input
word = "leetcoleet", k = 2
Output
3
Explanation
The blocks are `le`, `et`, `co`, `le`, `et`; keeping `le` (or `et`) needs the other three blocks replaced.

Example 3

Input
word = "aaaa", k = 1
Output
0

Constraints

  • 1 <= n == word.length <= 10^5
  • 1 <= k <= word.length
  • k divides word.length
  • word consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var minimumOperationsToMakeKPeriodic = function(word, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Operations to Make Word K-Periodic Solution

Minimum Number of Operations to Make Word K-Periodic solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Operations to Make Word K-Periodic is a medium coding problem on strings, hash table and counting, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Counting
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string word of length n and an integer k that divides n.

In one operation you pick two indices i and j, both divisible by k, and replace the length-k substring starting at i with the length-k substring starting at j — that is, word[i..i + k - 1] becomes a copy of word[j..j + k - 1].

The word is k-periodic if it equals some length-k string s repeated n / k times (for example, "ababab" is 2-periodic with s = "ab"). Return the minimum number of operations needed to make word k-periodic.

Example 1

Input: word = "codekatacode", k = 4
Output: 1
Explanation: Copy the block at index 0 over `kata`, giving `codecodecode`.

Example 2

Input: word = "leetcoleet", k = 2
Output: 3
Explanation: The blocks are `le`, `et`, `co`, `le`, `et`; keeping `le` (or `et`) needs the other three blocks replaced.

Example 3

Input: word = "aaaa", k = 1
Output: 0

Constraints

  • 1 <= n == word.length <= 10^5
  • 1 <= k <= word.length
  • k divides word.length
  • word consists only of lowercase English letters

Hints for Minimum Number of Operations to Make Word K-Periodic

  1. Hint 1

    An operation only ever copies a whole aligned block onto another aligned block. Split the word into its n / k blocks.

  2. Hint 2

    The final periodic word repeats a single block. Any block that already equals it needs no operation; every other block needs exactly one.

  3. Hint 3

    So choose the block value that occurs most often: the answer is n / k − (highest frequency). Count block frequencies in a hash map.

How to solve Minimum Number of Operations to Make Word K-Periodic

The operations copy existing aligned blocks, so the final word repeats one of the current blocks. Keep the most frequent block and overwrite every block that differs, one operation each.

Approach

  1. Cut word into the blocks word[i..i + k - 1] for i = 0, k, 2k, ….
  2. Count how many times each block string occurs.
  3. Return n / k − maxCount.

Why it works

Each operation changes one block, so a block that differs from the final pattern costs at least one operation, and one is enough (copy a block that already holds the pattern). The final pattern must be some existing block, because copies never create a new block value — so the best pattern is the most frequent block.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Only aligned blocks (starting at multiples of k) take part; overlapping substrings do not.
  • Counting characters instead of whole blocks gives the wrong answer — ab and ba are different blocks.

Reference solution

Python

from collections import Counter

def minimumOperationsToMakeKPeriodic(word: str, k: int) -> int:
    n = len(word)
    counts = Counter(word[i:i + k] for i in range(0, n, k))
    return n // k - max(counts.values())

Java

public static int minimumOperationsToMakeKPeriodic(String word, int k) {
    HashMap<String, Integer> counts = new HashMap<>();
    int best = 0;
    for (int i = 0; i < word.length(); i += k) {
        int c = counts.merge(word.substring(i, i + k), 1, Integer::sum);
        best = Math.max(best, c);
    }
    return word.length() / k - best;
}

C++

int minimumOperationsToMakeKPeriodic(string word, int k) {
    unordered_map<string, int> counts;
    int best = 0;
    for (size_t i = 0; i < word.size(); i += k) {
        best = max(best, ++counts[word.substr(i, k)]);
    }
    return (int) word.size() / k - best;
}

JavaScript

var minimumOperationsToMakeKPeriodic = function(word, k) {
    var counts = new Map();
    var best = 0;
    for (var i = 0; i < word.length; i += k) {
        var block = word.substring(i, i + k);
        var c = (counts.get(block) || 0) + 1;
        counts.set(block, c);
        if (c > best) best = c;
    }
    return word.length / k - best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets