What is the minimum number of operations to make word k-periodic?

The minimum number of operations is determined by the number of substring replacements required to turn the string into a k-periodic form, with the fewest operations achieved by maximizing the frequency of one substring.

How do I calculate the frequency of substrings in this problem?

Use a hash table to store the frequencies of k-length substrings that start at indices divisible by k. This allows you to quickly identify the most frequent substring and minimize operations.

What if the string is already k-periodic?

If the string is already k-periodic, no operations are needed, and the answer would be 0 operations.

How does this problem connect to Hash Table and String topics?

The problem requires using hash tables to efficiently count substrings, which is a key technique for optimizing solutions involving string manipulation and transformations.

Can this approach be used for other periodic string problems?

Yes, the same pattern of counting substrings and minimizing operations can be applied to other periodic string problems, but each variant may have unique constraints or requirements.

#3137

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

K 周期字符串需要的最少操作次数

给你一个长度为 n 的字符串 word 和一个整数 k ，其中 k 是 n 的因数。在一次操作中，你可以选择任意两个下标 i 和 j ，其中 0 ，且这两个下标都可以被 k 整除，然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。也就是说，将子串 word[i..i + …

哈希表字符串计数

题目描述

给你一个长度为 n 的字符串 word 和一个整数 k ，其中 k 是 n 的因数。

在一次操作中，你可以选择任意两个下标 i 和 j，其中 0 <= i, j < n ，且这两个下标都可以被 k 整除，然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。也就是说，将子串 word[i..i + k - 1] 替换为子串 word[j..j + k - 1] 。

返回使 word 成为 K 周期字符串 所需的最少操作次数。

如果存在某个长度为 k 的字符串 s，使得 word 可以表示为任意次数连接 s ，则称字符串 word 是 K 周期字符串 。例如，如果 word == "ababab"，那么 word 就是 s = "ab" 时的 2 周期字符串。

示例 1：

输入：word = "leetcodeleet", k = 4

输出：1

解释：可以选择 i = 4 和 j = 0 获得一个 4 周期字符串。这次操作后，word 变为 "leetleetleet" 。

示例 2：

输入：word = "leetcoleet", k = 2

输出：3

解释：可以执行以下操作获得一个 2 周期字符串。

i	j	word
0	2	etetcoleet
4	0	etetetleet
6	0	etetetetet

提示：

1 <= n == word.length <= 10⁵
1 <= k <= word.length
k 能整除 word.length 。
word 仅由小写英文字母组成。

lightbulb

解题思路

方法一：计数

我们可以将字符串 word 按照长度为 $k$ 的子串进行分组，然后统计每个子串出现的次数，最后返回 $n/k$ 减去出现次数最多的子串的次数即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 word 的长度。

1

2

3

4

5

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())

speed

复杂度分析

指标	值
时间	complexity depends on the final approach, but it generally involves iterating through the string and processing substrings, which gives an overall complexity of O(n). The space complexity is also O(n) due to the storage required for substring frequencies.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that makes use of hash tables for substring frequency calculation.
question_mark
Focus on the understanding of substring counting and minimizing operations based on frequency analysis.
question_mark
Evaluate how well the candidate can optimize the solution for large inputs by utilizing efficient data structures.

warning

常见陷阱

外企场景

error
Overcomplicating the problem by trying to manipulate the string directly instead of counting substring frequencies.
error
Failing to account for the fact that indices i and j must be divisible by k when performing operations.
error
Not considering edge cases, such as strings where no operations are needed or all characters are already the same.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if k does not divide n? In this case, the problem is invalid, so ensure the constraint k divides n is met.
arrow_right_alt
Consider the case where the string is already k-periodic, and no operations are needed.
arrow_right_alt
Explore variations where the operations involve multiple substrings at once or restricted to certain positions.

help

常见问题

外企场景

继续练习

#3138 同位字符串连接的最小长度 #3144 分割字符频率相等的最少子字符串 #3085 成为 K 特殊字符串需要删除的最少字符数