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

[antop-dev]

https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic

[antop-dev]

k 길이만큼 문자열을 반복되게 만드는데 실행되는 최소 연산 회수를 구하는 문제다.

Example 2:

word = "leetcoleet", k = 2

두 글자가 반복되어야 한다. 후보는 le, et, co다.

1. le → le et co le et → et co et 를 le로 3번 바꿔야 한다.
2. et → le et co le et → le co le 를 et로 3번 바꿔야 한다.
3. co → le et co le et → le et le et를 co로 4번 바꿔야 한다.

Kotlin:

class Solution {
    fun minimumOperationsToMakeKPeriodic(word: String, k: Int): Int {
        var maxCount = 0
        val hash = mutableMapOf<String, Int>() // <부분 문자열, 개수>
        for (i in word.indices step k) {
            val substring = word.substring(i, i + k)
            val count = hash[substring]?.let { it + 1 } ?: 1
            maxCount = maxOf(maxCount, count)
            hash[substring] = count
        }
        val total = word.length / k
        return total - maxCount
    }
}

Java:

import java.util.HashMap;

class Solution {
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        var len = word.length();
        var maxCount = 0;
        var hash = new HashMap<String, Integer>();
        for (var i = 0; i < len; i += k) {
            var substring = word.substring(i, i + k);
            var count = hash.getOrDefault(substring, 0) + 1;
            if (count > maxCount) maxCount = count;
            hash.put(substring, count);
        }
        var total = len / k;
        return total - maxCount;
    }
}

Python:

import collections

class Solution:
    def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
        length = len(word)
        counter = collections.defaultdict(lambda: 0)
        max_count = 0
        for i in range(0, length, k):
            substring = word[i:i + k]
            count = counter[substring] + 1
            max_count = max(max_count, count)
            counter[substring] = count

        total = length // k
        return total - max_count