给你一个长度为 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 <= 105
1 <= k <= word.length
k 能整除 word.length 。
word 仅由小写英文字母组成。
其实这个题挺好理解,就是将长度k的的子段(没有交集)提取出来,使得他们都相同,如何使操作步骤最小化,那肯定是按照子段重复次数最多的一种来复刻,结果最小。
那么问题就转化成如何找出重复次数最多的,两次遍历找肯定超时,所以用到工具map。
这里只简单的说下怎么用,原理和底层如何,需要的再去深究。
变量名称 := make(map[数据类型]键值类型)
变量名称 := make(map[数据类型]键值类型,长度)
m:=make(map[string]int)
遍历map
for k,v :=range m{
fmt.Println(k,v)
k是键,v是值
}
也可以值调用值
for v:=range m{
fmt.Println(v)
}
也可以进行排序
sort.Strings(m) //按照字符串遍历
func minimumOperationsToMakeKPeriodic(word string, k int) int {
l:=len(word)
m:=make(map[string]int)
for i:=0;i<l;i+=k{
s:=word[i:i+k]
m[s]++
}
sum:=0
for _,v:=range m{
//fmt.Println(k,v)
if v>sum{
sum=v
}
}
return l/k-sum
}